Codeforces Round #641 Div1.C Orac and Game of Life 中文题解
Caro23333
2020-04-30 00:26:59
### Orac and Game of Life 中文题解
称一个方格 $(i,j)$ 是好的，当且仅当至少有一个与 $(i,j)$ 相邻的方格颜色与 $(i,j)$ 相同。则经过一个回合后，好方格的颜色改变而不好的方格的颜色不变。
如果所有方格都是不好的，那么所有方格的颜色都始终不变。
显然，一个好方格 $(i,j)$ 以后不会变成不好的方格。
对于一个不好的方格 $(i,j)$，如果有至少一个好的方格 $(i',j')$ 与之相邻，由于 $(i,j)$ 不好，所以 $(i,j)$ 与 $(i',j')$ 颜色不同，在一个回合后，$(i,j)$ 的颜色不变而 $(i',j')$ 的颜色改变，于是 $(i,j)$ 变成了好的；反之，如果与 $(i,j)$ 相邻的方格都是不好的，在一个回合后，$(i,j)$ 以及与 $(i,j)$ 相邻的方格颜色都不变，因此 $(i,j)$ 仍然是不好的。
因此，对于一个方格 $(i,j)$， $(i,j)$ 第一次成为好方格的所需要的回合数 $f_{i,j}$ 等于 $(i,j)$ 到达一个好方格的最短曼哈顿距离。于是，可以通过BFS求出 $f_{i,j}$。
注意到，对于 $k \le f_{i,j}$，在第 $k$ 个回合中， $(i,j)$ 的颜色不变；对于 $k>f_{i,j}$，在第 $k$ 个回合中，$(i,j)$ 的颜色变化。于是可以 $O(1)$ 回答每个询问，总复杂度 $O(nm+t)$ 。
Problem and Tutorial by AKEE
谨以此题献 **John Horton Conway**，一位值得我们铭记的数学家。愿您安息。
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN = 1005;
inline ll readint()
{
ll res = 0, f = 1;
char c = 0;
while(!isdigit(c))
{
c = getchar();
if(c=='-')
f = -1;
}
while(isdigit(c))
res = res*10+c-'0', c = getchar();
return res*f;
}
int n,m,T,a[MAXN][MAXN];
char str[MAXN];
int f[MAXN][MAXN],pos[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
bool vis[MAXN][MAXN];
inline bool check(int x, int y)
{
for(int i = 0; i<4; i++)
{
int nx = x+pos[i][0], ny = y+pos[i][1];
if(a[nx][ny]==a[x][y])
return true;
}
return false;
}
pii q[MAXN*MAXN];
inline void bfs()
{
int front = 0, rear = 0;
for(int i = 1; i<=n; i++)
for(int j = 1; j<=m; j++)
if(check(i,j))
f[i][j] = 0, vis[i][j] = true, q[rear++] = mp(i,j);
while(front<rear)
{
pii now = q[front++];
for(int i = 0; i<4; i++)
{
int nx = now.fi+pos[i][0], ny = now.se+pos[i][1];
if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny])
continue;
f[nx][ny] = f[now.fi][now.se]+1;
vis[nx][ny] = true;
q[rear++] = mp(nx,ny);
}
}
}
int main()
{
n = readint(), m = readint(), T = readint();
memset(a,-1,sizeof(a));
for(int i = 1; i<=n; i++)
{
scanf("%s",str+1);
for(int j = 1; j<=m; j++)
a[i][j] = str[j]-'0';
}
bfs();
int x,y;
ll t;
while(T--)
{
x = readint(), y = readint(), t = readint();
if(vis[x][y])
printf("%d\n",a[x][y]^(max(0ll,t-f[x][y])&1));
else
printf("%d\n",a[x][y]);
}
return 0;
}
```