JOI過去問の質問です。

[ふぇると]

またまたお世話になります。
2014年第5問です。
公式解説

コード:

#include <iostream>
#include <queue>
using namespace std;

int H, W;
char field[1005][1005];
queue<pair<int, int>> Q[2];
pair<int, int> i_j(0, 0);

int check(int i, int j) {
	if (field[i][j] == '.')  return 0;

	int sarachi_count = 0;
	for (int p = 0; p < 3; p++) {
		for (int q = 0; q < 3; q++) {
			if (field[i - 1 + p][j - 1 + q] == '.') { sarachi_count++; }
		}
	}

	int field_data = atoi(&field[i][j]);


	if (sarachi_count >= field_data)  return 1;  // 崩れる

	return 0; // 崩れない
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> field[i][j];
		}
	}

	int wave_count = 0;
	// 最初の全チェック
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			int res = check(i, j);
			switch (res) {
			case 0:
				break;
			case 1:
				Q[0].push(make_pair(i, j)); // 崩れるマス記録
				break;

			}
		}
	}
	wave_count++;

	while (!Q[0].empty() || !Q[1].empty()) {

		while (!Q[0].empty()) {
			i_j = Q[0].front();
			Q[0].pop();
			for (int p = 0; p < 3; p++) {
				for (int q = 0; q < 3; q++) {
					int res = check(i_j.first - 1 + p, i_j.second - 1 + q);
					switch (res) {
					case 0:
						break;
					case 1:
						Q[1].push(make_pair(i_j.first, i_j.second)); // 崩れるマス記録
						break;
					}
				}
			}
		}
		while (!Q[1].empty()) {
			i_j = Q[1].front();
			field[i_j.first][i_j.second] = '.';
			Q[0].push(Q[1].front());
			Q[1].pop();
		}
		wave_count++;
	}
	

	cout << wave_count;

	return 0;
}

以下のコードを実行させると、入出力例1だとうまくいくのですが、2だとQ[0]が空っぽのままでうまくwhileループに入ってくれません。
原因は何でしょうか？

[みけCAT]

• atoiは文字列を数値に変換するので、atoi(&field[j])でそのマスの値を得ることは一般にできません。(Q[0]が空っぽのままである原因)
• 67行目で正しく崩れるマスを記録していません。(無限ループになる原因)
• 最初にチェックした後崩していないので、二重に数えてしまうなど誤動作します。

修正してみました。

コード:

#include <iostream>
#include <queue>
using namespace std;

int H, W;
char field[1005][1005];
queue<pair<int, int>> Q[2];
pair<int, int> i_j(0, 0);
 
int check(int i, int j) {
	if (field[i][j] == '.')  return 0;
	int sarachi_count = 0;
	for (int p = 0; p < 3; p++) {
		for (int q = 0; q < 3; q++) {
			if (field[i - 1 + p][j - 1 + q] == '.') { sarachi_count++; }
		}
	}

	int field_data = field[i][j] - '0';


	if (sarachi_count >= field_data)  return 1;  // 崩れる

	return 0; // 崩れない
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> field[i][j];
		}
	}

	int wave_count = 0;
	// 最初の全チェック
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			int res = check(i, j);
			switch (res) {
			case 0:
				break;
			case 1:
				Q[1].push(make_pair(i, j)); // 崩れるマス記録
				break;

			}
		}
	}

	while (!Q[0].empty() || !Q[1].empty()) {

		while (!Q[1].empty()) {
			i_j = Q[1].front();
			field[i_j.first][i_j.second] = '.';
			Q[0].push(Q[1].front());
			Q[1].pop();
		}
		wave_count++;

		while (!Q[0].empty()) {
			i_j = Q[0].front();
			Q[0].pop();
			for (int p = 0; p < 3; p++) {
				for (int q = 0; q < 3; q++) {
					int res = check(i_j.first - 1 + p, i_j.second - 1 + q);
					switch (res) {
					case 0:
						break;
					case 1:
						Q[1].push(make_pair(i_j.first - 1 + p, i_j.second - 1 + q)); // 崩れるマス記録
						break;
					}
				}
			}
		}
	}
	

	cout << wave_count;

	return 0;
}

0～9の数字の文字コードは規格上連続しているので、field[j] - '0'でそのマスの数値が求まります。

In both the source and execution basic character sets, the value of each character after 0 in the
above list of decimal digits shall be one greater than the value of the previous.

(http://www.open-std.org/jtc1/sc22/wg21/ ... /n3337.pdf)

[ふぇると]

• atoiは文字列を数値に変換するので、atoi(&field[j])でそのマスの値を得ることは一般にできません。(Q[0]が空っぽのままである原因)
• 67行目で正しく崩れるマスを記録していません。(無限ループになる原因)
• 最初にチェックした後崩していないので、二重に数えてしまうなど誤動作します。

文字列のままでよかったんですね…。
ありがとうございました。非常に参考になりました。

[ふぇると]

ところで、このコードで実行すると入出力4,5がうまくいきませんでした。
サンプルコードでうまくいくことを考えると、これは無駄が大きいコードだったのでしょうか？