気づけば簡単なのだけど、本番気づかなかった。
http://code-festival-2014-china-open.contest.atcoder.jp/tasks/code_festival_china_i
問題
N*Nのグリッドがある。各セルは白か黒の何れかである。
プレイヤーは最初(0,0)のセルにおり、隣接セルを辿って(N-1,N-1)に移動したい。
移動の度、敵は白マスの1か所をふさぎ、プレイヤーの移動を防止することができる。
敵がどのように白マスをふさいでも、プレイヤーが目的地に移動できるかどうか答えよ。
解法
目的地から逆向きに「目的地に到達可能なセル」の集合を求めていく。
「目的地に到達可能なセル」は、隣接マスに「目的地に到達可能な黒セル」があるか、目的地に到達可能な白セル」が2個以上ある場合である。
よって目的地からBFSし、隣接マスに「目的地に到達可能な黒セル」「目的地に到達可能な白セル」の数を加算していくことで、順次「目的地に到達可能なセル」を求めることができる。
int N; string S[1001]; int num[1001][1001],vis[1001][1001]; void solve() { int i,j,k,l,r,x,y,x2,y2; string s; cin>>N; FOR(y,N) cin>>S[y]; num[N-1][N-1]=2; vis[N-1][N-1]=1; queue<int> Q; Q.push((N-1)*1000+(N-1)); while(Q.size()) { int k=Q.front(); Q.pop(); int cy=k/1000,cx=k%1000; FOR(i,4) { int dd[4]={0,1,0,-1}; int ty=cy+dd[i],tx=cx+dd[i^1]; if(tx<0||ty<0||tx>=N||ty>=N) continue; if(vis[ty][tx]) continue; num[ty][tx]++; if(S[cy][cx]=='#') num[ty][tx]+=2; if(num[ty][tx]>=2) vis[ty][tx]=1, Q.push(ty*1000+tx); } } if(vis[0][0]) _P("YES\n"); else _P("NO\n"); }
まとめ
本番思いつかなかったなぁ。