問題ページ
サンプル1,2のようにすべてのマスについて同じ色が隣接、もしくは異なる色と隣接しているような状況のときは明らか。そうではないケースについて、とりあえず実験してみる。
01 01 00
10 → 11 → 00
00 11 00
同じ色が隣接しているマスが一つ以上存在した場合、同じ色が連結なマスがどんどん増えていくので、明らかなケースに行き着くまでのiteration数は 
で抑えられる。各マスについて色変化をはじめるiterationがいつなのかを求めたい。
21
10
00
最初から同じ色が隣接している場合は0、そのマスに隣接している場合は1、さらに隣接している場合は2 …となっていることがわかる。0のマスからスタートする多点スタートBFSによって、各マスの色変化を始めるiterationが求められる。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
const ll INF = 1LL<<30;
int main(void) {
ll h, w, t;
cin >> h >> w >> t;
vector<string> s(h);
REP(i, h) cin >> s[i];
queue<PII> que;
vector<vector<int>> dist(h, vector<int>(w, INF));
ll dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
REP(i, h) REP(j, w) {
REP(k, 4) {
ll ny = i + dy[k], nx = j + dx[k];
if(nx<0 || nx>=w || ny<0 || ny>=h) continue;
if(s[i][j]==s[ny][nx]) {
dist[i][j] = 0;
que.push({i, j});
}
}
}
while(que.size()) {
PII p = que.front(); que.pop();
ll i = p.first, j = p.second;
REP(k, 4) {
ll ny = i + dy[k], nx = j + dx[k];
if(nx<0 || nx>=w || ny<0 || ny>=h) continue;
if(dist[ny][nx] == INF) {
dist[ny][nx] = dist[i][j] + 1;
que.push({ny, nx});
}
}
}
REP(i, t) {
ll y, x, k;
cin >> y >> x >> k;
y--, x--;
if(dist[y][x] == INF || k <= dist[y][x]) {
cout << s[y][x] << "\n";
} else {
ll p = (k - dist[y][x]) % 2;
if(p == 0) {
cout << s[y][x] << "\n";
} else {
cout << (char)((1-(s[y][x]-'0')) + '0') << "\n";
}
}
}
return 0;
}
