Solution #
Let’s call a cell bad if no adjacent cell has the same color, otherwise that cell is good.
If a good cell and a bad cell are adjacent, according to the definition, the good cell will change color in the next iteration while the bad cell not. As the result, the bad cell will turn into a good cell. Therefore, a bad cell won’t change if all the cells are bad cells, otherwise it will become good when the nearest good cell reaches it. The left thing is to find the nearest good cell for all cells. This can be done using multi-source bfs.
Code #
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
template<typename... T> void rd(T&... args) {((cin>>args), ...);}
template<typename... T> void wr(T... args) {((cout<<args<<" "), ...);cout<<endl;}
const vector<pii> dir{{1,0,},{-1,0},{0,1},{0,-1}};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,t;
cin>>n>>m>>t;
vector<string> G(n);
for(auto& it:G) cin>>it;
queue<pii> q;
auto cango=[&](int x,int y){
return x>=0&&x<n&&y>=0&&y<m;
};
vector<vector<int>> dis(n,vector<int>(m,-1));
forn(i,n){
forn(j,m){
bool ok=0;
for(auto [dx,dy]:dir){
int x=i+dx,y=j+dy;
if(cango(x,y)&&G[x][y]==G[i][j]) ok=1;
}
if(ok){
dis[i][j]=0;
q.emplace(i,j);
}
}
}
while(!q.empty()){
auto [i,j]=q.front();
q.pop();
for(auto [dx,dy]:dir){
int x=i+dx,y=j+dy;
if(cango(x,y)&&dis[x][y]==-1){
dis[x][y]=dis[i][j]+1;
q.emplace(x,y);
}
}
}
while(t--){
int i,j;
ll p;
cin>>i>>j>>p;
i--,j--;
if(dis[i][j]==-1) cout<<G[i][j]<<endl;
else if(dis[i][j]>=p) cout<<((G[i][j]-'0'))<<endl;
else cout<<((G[i][j]-'0')^((p-dis[i][j])&1))<<endl;
}
return 0;
}