题解 CF1349C 【Orac and Game of Life】

考虑到，如果有两个挨在一起的同色格子，则下一时刻它们肯定还是同色。 也就是说，我们可以把同色的格子缩成一个点，它们每个时刻的状态是一样的！ ```plain 01010 11101 01010 ``` 比如上面这个栗子，左边那个呈十字的 $1$ 连通块颜色一定每个时刻都相同。 然后再考虑变化一个时刻之后，每个大连通块颜色都会取反。这时候如果周围有四周颜色都与其不同的格子的话，这种格子就会并入大连通块中。例如上面的图，在下一时刻就会变成： ```plain 00010 00001 00010 ``` 之前 $1$ 连通块的十字全变成了 $0$，然后就将周围的 $0$ 也并入大连通块里头了。 不难发现，除非整个图都是 $01$ 交错，否则任何一个单独的点都能被大连通块并入。 那么我们考虑一遍 $\rm BFS$ 求出每个点在哪个时刻，被并入一个初始颜色是啥的大连通块中，就能直接计算第 $p$ 时刻其颜色了。 复杂度 $O(nm+q)$。 $\rm Code$： ```cpp int n, m, q; char s[1010][1010]; int bel[1010][1010]; int tim[1010][1010]; struct Node { int x, y; Node() {} Node(int x, int y):x(x), y(y) {} }; queue<Node>Q; inline int chk(Node x) { return 1 <= x.x && x.x <= n && 1 <= x.y && x.y <= m; } int main() { memset(bel, -1, sizeof(bel)); scanf("%d%d%d", &n, &m, &q); for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { int tmp = 0; tmp |= s[i][j] == s[i - 1][j]; tmp |= s[i][j] == s[i + 1][j]; tmp |= s[i][j] == s[i][j - 1]; tmp |= s[i][j] == s[i][j + 1]; if(tmp) { bel[i][j] = s[i][j] - 48; Q.push(Node(i, j)); } } while(!Q.empty()) { Node x = Q.front(); Q.pop(); Node t; t = Node(x.x + 1, x.y); if(chk(t) && bel[t.x][t.y] == -1) Q.push(t), bel[t.x][t.y] = bel[x.x][x.y], tim[t.x][t.y] = tim[x.x][x.y] + 1; t = Node(x.x - 1, x.y); if(chk(t) && bel[t.x][t.y] == -1) Q.push(t), bel[t.x][t.y] = bel[x.x][x.y], tim[t.x][t.y] = tim[x.x][x.y] + 1; t = Node(x.x, x.y + 1); if(chk(t) && bel[t.x][t.y] == -1) Q.push(t), bel[t.x][t.y] = bel[x.x][x.y], tim[t.x][t.y] = tim[x.x][x.y] + 1; t = Node(x.x, x.y - 1); if(chk(t) && bel[t.x][t.y] == -1) Q.push(t), bel[t.x][t.y] = bel[x.x][x.y], tim[t.x][t.y] = tim[x.x][x.y] + 1; } while(q--) { int x = ri, y = ri; ll k = rl; if(bel[x][y] == -1 || k < tim[x][y]) putchar(s[x][y]); else putchar(48 | (bel[x][y] ^ (k & 1))); puts(""); } return 0; } ```