Codeforces Round #641 (Div. 1) C. Orac and Game of Life

問題ページ

サンプル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;  
}