https://codeforces.com/contest/1350/problem/E
1.首先预处理出所有从一开始就可以变色的连通块，把点集加入队列中去。
2.然后做一个bfs，最短路的思路，把可以变色的连通块向四周“感染”。
3.d[][]数组记录一个被感染的时间。初始时，可以变色的连通块d[][]为0，向四周时，就是最短路思路了，查询时，如果时间小于p，则说明还没有变色，如果时间大于p，d-p为奇数则为变色，偶数则变为原色。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e3+5; 5 const int inf = 0x3f3f3f3f; 6 int dx[4] = {1,-1,0,0,},dy[4] = {0,0,-1,1}; 7 int n,m,t; 8 char s[maxn][maxn]; 9 int d[maxn][maxn]; 10 void init(){ 11 memset(d,0x3f3f3f3f,sizeof(d)); 12 // cout<<"x"; 13 queue<pair<int,int> > q; 14 for (int i = 1;i<=n; ++i) 15 { 16 for(int j = 1;j<=m;++j){ 17 18 bool f = 0; 19 for (int k = 0; k <4; ++k) 20 { 21 int tx = i + dx[k],ty = j + dy[k]; 22 if(tx>=1 && tx<=n && ty>=1 && ty<=m && s[tx][ty] == s[i][j]) f = 1; 23 /* code */ 24 } 25 if(!f) continue; 26 q.push({i,j}); 27 d[i][j] = 0; 28 } 29 /* code */ 30 } 31 while(!q.empty()){ 32 int x = q.front().first,y = q.front().second; 33 q.pop(); 34 for (int i = 0; i < 4; ++i) 35 { 36 int tx = x + dx[i],ty = y + dy[i]; 37 if(tx>=1 && tx<=n && ty>=1 && ty<=m && d[tx][ty] > d[x][y] + 1){ 38 d[tx][ty] = d[x][y] + 1; 39 q.push({tx,ty}); 40 41 } 42 /* code */ 43 } 44 } 45 } 46 int main(){ 47 scanf("%d%d%d",&n,&m,&t); 48 for (int i = 1; i <=n; ++i) 49 { 50 scanf("%s",s[i]+1); 51 /* code */ 52 } 53 init(); 54 while(t--){ 55 int i,j; 56 ll p; 57 scanf("%d%d%lld",&i,&j,&p); 58 if(d[i][j] == inf){ 59 printf("%c ",s[i][j] ); 60 continue; 61 } 62 if(p<=d[i][j]) printf("%c ", s[i][j]); 63 else { 64 int cur = s[i][j] - '0'; 65 if((p-(ll)d[i][j])&1) printf("%d ",cur^1 ); 66 else printf("%d ",cur ); 67 } 68 } 69 return 0; 70 }