CF#301は不参加なので練習。
B,Cが妙にコーナーケースが多くてはまった。
http://codeforces.com/contest/540/problem/C
問題
2次元グリッドが与えられる。
各セルは壊れやすい氷か頑丈な氷である。
壊れやすい氷のセルは、乗ると即座に壊れて下の階に落とされる。
頑丈な氷のセルは、一旦乗ることができるがその時点で壊れやすい氷のセルになり、再度乗ると下の階に落とされる。
グリッド上で始点と終点の2つセル位置が指定される。
始点セルから初めて隣接セルを辿って移動していく場合、終点セルで下の階に落ちることは可能か。
解法
終点セルが壊れやすいなら、そこに到達可能なら問題文の条件を満たす。
終点セルが頑丈なら、そこに到達する経路以外で、終点セルの隣接1つ頑丈なセルがあればよい。
実際は場合分けが気味にめんどくさい。
- 始点==終点の場合:
- 終点セルが頑丈なら、隣接セルに頑丈なセルが2個以上あればよい。
- 終点セルが壊れやすいなら、隣接セルに頑丈なセルが1個以上あればよい。
- 始点と終点の距離が1の場合:
- 終点セルが頑丈なら、隣接セルに頑丈なセルが1個以上あればよい。
- 終点セルが壊れやすいなら、条件を満たせる。
- 始点と終点の距離が2以上の場合:
- まず前提として、始点の頑丈な隣接セルから、頑丈なセルだけたどって終端の隣接セルに行けること。
- これはBFSなりUnion-Findで検索可能。
- その上で、終点セルが頑丈なら、隣接セルに頑丈なセルが2個以上あればよい。
- まず前提として、始点の頑丈な隣接セルから、頑丈なセルだけたどって終端の隣接セルに行けること。
template<int um> class UF { public: vector<int> par,rank,cnt; UF() {rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par.push_back(i);} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int count(int x) { return cnt[operator[](x)];} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; cnt[y]=cnt[x]=cnt[x]+cnt[y]; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; UF<500000> uf; int H,W; string S[1010]; int X[2],Y[2]; int getadjok(int y,int x) { int num=0; if(y>0 && S[y-1][x]=='.') num++; if(y<H-1 && S[y+1][x]=='.') num++; if(x>0 && S[y][x-1]=='.') num++; if(x<W-1 && S[y][x+1]=='.') num++; return num; } void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W; FOR(y,H) cin>>S[y]; FOR(y,H) FOR(x,W) if(S[y][x]=='.') { if(x<W-1 && S[y][x+1]=='.') uf(y*500+x,y*500+x+1); if(y<H-1 && S[y+1][x]=='.') uf(y*500+x,(y+1)*500+x); } FOR(i,2) cin>>Y[i]>>X[i], Y[i]--,X[i]--; if(abs(X[1]-X[0])+abs(Y[1]-Y[0])<=1) { int adj=abs(X[1]-X[0])+abs(Y[1]-Y[0]); if(S[Y[1]][X[1]]=='.' && getadjok(Y[1],X[1])+adj>=2) return _P("YES\n"); if(S[Y[1]][X[1]]=='X' && getadjok(Y[1],X[1])+adj>=1 && H*W>1) return _P("YES\n"); } else if(S[Y[1]][X[1]]=='.') { int ok=0; FOR(i,4) { int dd[]={-1,0,1,0}; int ty=Y[0]+dd[i],tx=X[0]+dd[i^1]; if(tx>=0 && tx<W && ty>=0 && ty<H && uf[ty*500+tx]==uf[Y[1]*500+X[1]] && S[ty][tx]!='X') ok=1; } if(ok && getadjok(Y[1],X[1])>=2) return _P("YES\n"); } else { FOR(i,16) { int dd[]={-1,0,1,0}; int ty=Y[0]+dd[i%4],tx=X[0]+dd[(i%4)^1]; int sy=Y[1]+dd[i/4],sx=X[1]+dd[(i/4)^1]; if(tx<0 || tx>=W || ty<0 || ty>=H) continue; if(sx<0 || sx>=W || sy<0 || sy>=H) continue; if(uf[ty*500+tx]==uf[sy*500+sx] && S[ty][tx]!='X' && S[sy][sx]!='X') return _P("YES\n"); } } _P("NO\n"); }
まとめ
Editorial見ても細かく場合分けしてるけど、DFSでさらっと短く書いてる人もいるね。