いくらなんでも 2 分で解ける問題とは思えないのですが...
問題概要
2 × N のグリッドが与えられる。最初はグリッドのマスはすべて「通路」の状態であって、マス (1, 1) からマス (2, N) に到達することができる。以下の q 個のクエリに答えよ。
- 回目のクエリは (r, c) で与えられ、その時点でもしマス (r, c) が「通路」ならば「壁」になり、「壁」ならば「通路」となる。
- その処理を行った後で、(1, 1) から (2, N) へ到達できるかどうかを判定せよ
制約
考えたこと
これそんなに簡単なの!?
通り抜けられる条件は、以下の条件を満たすことと同値である (0-indexed に直している)
- 任意の (r, c) に対して、以下のすべてが成立する:
- (r, c) と (1-r, c-1) のどちらかは通路である
- (r, c) と (1-r, c) のどちらかは通路である
- (r, c) と (1-r, c+1) のどちらかは通路である
そこで、この条件の違反している部分の個数を常に更新することで、クエリに答えることができる。
#include <iostream> #include <vector> using namespace std; int main() { int N, Q; cin >> N >> Q; vector<vector<int> > turo(2, vector<int>(N, 1)); int dame = 0; for (int q = 0; q < Q; ++q) { int r, c; cin >> r >> c; --r, --c; // 新たに壁に if (turo[r][c]) { for (int dc = -1; dc <= 1; ++dc) { int nc = c + dc; if (nc < 0 || nc >= N) continue; if (!turo[1-r][nc]) ++dame; } turo[r][c] = false; } // 壁を消す else { for (int dc = -1; dc <= 1; ++dc) { int nc = c + dc; if (nc < 0 || nc >= N) continue; if (!turo[1-r][nc]) --dame; } turo[r][c] = true; } if (!dame) cout << "Yes" << endl; else cout << "No" << endl; } }