Codeforces Round #641 (Div. 2) E. Orac and Game of Life（bfs+思维）

题目链接

题意：给定一个黑白网格，每一轮会对这个黑白网格进行变换，规则是如果一个单元格中只要有一个单元格和它有相同的颜色，那么它就变色，给出x，y，p，问第p轮的时候（x，y）的颜色。
思路：首先感谢这场比赛，成功上紫。

其实这个也挺水的，不知道为什么没人做。
首先可以模拟一下，如果一旦一个格子变色的话，最终会慢慢殃及其他所有的格子变色（就是时间早晚的问题），如果一旦一个格子变了色，那么在剩下的轮变换中呈现周期性变换，也就是从它变色的那一刻起（如果是奇数轮了就是变色，偶数轮又变回来了）。于是现在的重点就是看这个格子第一次变色的时间，我们可以bfs一下，先把所有第一次就变色的格子push进队列，接着宽搜（因为宽搜一定是时间最短的）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+5;
char s[maxn][maxn];
const int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
int n,m,vis[maxn][maxn];
bool check(int x, int y)
{
	return x>=1&&x<=n&&y>=1&&y<=m&&vis[x][y]==-1;
}
struct cxk{
	int x,y,step;
};
bool check2(int  x , int y , char xx)
{
	for(int i=0;i<4;++i)
	if(s[x+dir[i][0]][y+dir[i][1]]==xx) return true;
	return false;
}
void bfs()
{
		queue<cxk>q;
		for(int i=1;i<=n;++i) 
		for(int j=1;j<=m;++j)
		if(check2(i,j,s[i][j])) q.push({i,j,0}),vis[i][j]=0;//找第一次就变色的点 
	while(!q.empty())
	{
		cxk t=q.front();
		q.pop();
		for(int i=0;i<4;++i)
		{
			int nx=t.x+dir[i][0],ny=t.y+dir[i][1];
			if(check(nx,ny))
			q.push({nx,ny,t.step+(s[nx][ny]==s[t.x][t.y]?0:1)}),vis[nx][ny]=t.step+((s[nx][ny]==s[t.x][t.y])?0:1);
		}
	}
}
int main()
{
	memset(vis,-1,sizeof(vis));
	int x,y,t;
	ll p;
	cin>>n>>m>>t;
	for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
	bfs();
	while(t --)
	{
		scanf("%d %d %lld",&x,&y,&p);
		ll ans = s[x][y] - '0';
		if(vis[x][y] >= 0 && p > vis[x][y] && (p - vis[x][y]) & 1) ans ^= 1;
		printf("%lld\n",ans);
	}
}