隣接する白く塗られたマスと黒く塗られたマスについて考えると、操作を行ったとき白く塗られたマスは黒に、黒く塗られたマスは白に塗り替わります。特に、ある時点で黒く塗られ、隣接する白く塗られたマスが存在するようなマスはその後操作をするたびに黒く塗られた状態と白く塗られた状態を交互に繰り返します。

ここで、\(1\) 回以上の操作を行って得られるマス目について、黒く塗られたマスは、隣接する白く塗られたマスを持ちます。これは、操作を行う前の状況を考えると操作後に黒く塗られたマスは操作前に黒く塗られた隣接するマスを持つはずであり、これは操作後には白く塗られた隣接するマスになっているためです。

したがって、まずは \(1\) 回操作を行い、その後に初めてマスが黒く塗られるタイミング（の偶奇）が各マスについてわかればこの問題を解くことができます。

初めてマスが黒く塗られるまでには最も近い黒マスからの距離と同じだけの操作回数がかかり、これは（多始点）BFS により求めることができます。時間計算量は \(O(HW)\) です。

なお、\(1\) 回操作後に黒マスが存在しない場合に注意してください。下の実装例では inf を偶数に取ることで場合分けをせずに実装しています。

実装例

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
const int inf = 1000000010;
vector<int> dx = { 1,0,-1,0,1,-1,-1,1 }, dy = { 0,1,0,-1,1,1,-1,-1 };

int main() {
	int n, m;
	cin >> n >> m;
	vector<string> a(n);
	rep(i, n) cin >> a[i];

	auto in = [&](int x, int y) {return 0 <= x && x < n && 0 <= y && y < m; };

	vector<string> b(n, string(m, '.'));
	rep(i, n) rep(j, m) {
		if (a[i][j] == '#') {
			rep(d, 8) {
				int x = i + dx[d], y = j + dy[d];
				if (in(x, y) && a[x][y] == '.') b[x][y] = '#';
			}
		}
	}
	a = move(b);

	vector D(n, vector<int>(m, inf));
	queue<pair<int, int>> Q;
	rep(i, n) rep(j, m) if (a[i][j] == '#') { D[i][j] = 0; Q.push({ i, j }); }
	while (!Q.empty()) {
		auto [i, j] = Q.front(); Q.pop();
		rep(d, 8) {
			int x = i + dx[d], y = j + dy[d];
			if (in(x, y) && D[x][y] == inf) {
				D[x][y] = D[i][j] + 1;
				Q.push({ x, y });
			}
		}
	}
	rep(i, n) {
		rep(j, m) a[i][j] = (D[i][j] % 2 == 0 ? '.' : '#');
		cout << a[i] << '\n';
	}
}