750ptということもあってBの割に簡単。
http://codeforces.com/contest/585/problem/B
問題
縦3行、横W列のグリッドがある。
自分は左端の列のどこかにいる。
グリッド上いくつか電車があるマスがある。
時間1ごとに、自分と電車は交互に以下の順でように動く。
- 自分が1マス右に移動する。
- 次に、上下に最大1マス動いても良い。
- 次に各電車は左に2マス動く。
右からやってくる電車にぶつからずやり過ごしながら、自分が右端に到達できるか判定せよ。
解法
電車が左に2マス動くと考えると面倒なので、自分が右に2マス動くと考えると、後は単純な探索。
int T; int W,N; string S[3]; void solve() { int i,j,k,l,r,x,y,z; string s; cin>>T; while(T--) { cin>>W>>N; FOR(i,3) cin>>S[i], S[i]+="................"; W+=15; for(x=0;x+3<W;x+=3) { FOR(y,3) if(S[y][x]=='s') { if(S[y][x+1]!='.' && S[y][x+1]!='s' ) continue; for(z=max(0,y-1);z<=min(2,y+1);z++) if(S[z][x+1]=='.') S[z][x+1]='s'; } FOR(y,3) if(S[y][x+1]=='s' && S[y][x+2]=='.') S[y][x+2]='s'; FOR(y,3) if(S[y][x+2]=='s' && S[y][x+3]=='.') S[y][x+3]='s'; } if(S[0][W-5]=='s' || S[1][W-5]=='s' || S[2][W-5]=='s') cout<<"YES"<<endl; else cout<<"NO"<<endl; } }
まとめ
Div1Bにしては解法にヒネリが無さすぎる気がするが…。