Darker and Darker [AtCoder Grand Contest 033 A]

https://atcoder.jp/contests/agc033/tasks/agc033_a

前提知識

• 幅優先探索

解説

https://atcoder.jp/contests/agc033/submissions/5269426

シミュレーションをしよう。
効率的にシミュレーションをするために幅優先探索として行う。
操作では「隣接のマスに黒色のマスがあれば、白色のマスが黒色になる」とあるが、
これを「黒色のマスの周りを黒色にする」と考えることもできる。
こう考えることにすると、あるターンである黒色のマスの周りを黒色にすると、
それ以降のターンでその黒色のマスの周りを再度黒色にすることはありえない。
つまり、一度周りを黒色にしたマスはそれ以降のターンで黒色にする操作をしなくてもいいということになる。
この要領でシミュレーションを行っていき、かかったターンを数えると答え。

int H, W;
string A[1010];
int vis[1010][1010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> H >> W;
	rep(y, 0, H) cin >> A[y];
 
	queue<pair<int, int>> que;
	rep(y, 0, H) rep(x, 0, W) if (A[y][x] == '#') {
		vis[y][x] = 1;
		que.push({ x,y });
	}
 
	int ans = 0;
	while (!que.empty()) {
		queue<pair<int, int>> que2;
 
		while (!que.empty()) {
			int x, y;
			tie(x, y) = que.front(); que.pop();
 
			rep(d, 0, 4) {
				int xx = x + dx[d];
				int yy = y + dy[d];
				if (xx < 0 or W <= xx or yy < 0 or H <= yy) continue;
				if (!vis[yy][xx]) {
					vis[yy][xx] = 1;
					que2.push({ xx,yy });
				}
			}
		}
 
		swap(que2, que);
		ans++;
	}
	cout << ans-1 << endl;
}