Consider a pair of adjacent cells painted white and black. An operation turns the white cell into black, and black into white. In particular, if a cell is painted black and there exists a white adjacent cell at some point, it alternately switches between black and white indefinitely onward by an operation.

Here, for a gird state that can be obtained by performing one or more operations, any black cell has an adjacent white cell. This is because a black cell after an operation must have an adjacent cell that was black before the operation, which becomes white after the operation.

Therefore, the problem can be solved by first applying an operation once, and the finding (the parity of) how many more operations are required before each cell becomes black for the first time after that.

The number of operation required until it turns black for the first time is equal to the distance form a closest black cell, which can be found with a (multi-source) BFS (Breadth-First Search). The complexity is \(O(HW)\).

Note that there is a case where there is no black cell after one operation. In the sample code below, we avoid casework by setting inf to an even number.

Sample code

#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';
	}
}