题解 CF1349C 【Orac and Game of Life】
CYJian
2020-05-13 08:32:59
考虑到,如果有两个挨在一起的同色格子,则下一时刻它们肯定还是同色。
也就是说,我们可以把同色的格子缩成一个点,它们每个时刻的状态是一样的!
```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;
}
```