PKU 1382 The Proper Key
http://poj.org/problem?id=1382
鍵の形とそれを入れる錠前の形が与えられるので、鍵がどこまでささるかを答えろというような問題。
制約がやたら大きいが、多少愚直な方法でも通るようです。
bfsしました。
sync_with_stdio(false)なのにcoutとprintfを使っていてはまりました。
string keyline; void solve(){ vector<PI> key; int r,c; cin>>r>>c; rep(i,r){ cin>>keyline; rep(j,c) if(keyline[j]=='#') key.pb(mp(i,j)); } int d,w; cin>>d>>w; string lock[d]; rep(i,d) cin>>lock[i]; bool vis[2][w]; memset(vis,0,sizeof(vis)); queue<PI> q; for(int i=0;i+c<=w;++i){ q.push(mp(0,i)); vis[0][i]=true; } int ans=0; int idx=0; int dx[]={1,0,0},dy[]={0,1,-1}; while(true){ if(q.empty()) break; queue<PI> nque; ++idx; memset(vis[idx&1],0,sizeof(vis[0])); while(!q.empty()){ int cx=q.front().F; int cy=q.front().S; q.pop(); //cout<<cx<<' '<<cy<<endl; ans=max(cx,ans); if(cx>=d+r){ cout<<"The key can fall through."<<endl; return; } rep(i,3){ int nx=cx+dx[i],ny=cy+dy[i]; if(min(nx,ny)<0 || ny+c>w || vis[nx&1][ny]) continue; vis[nx&1][ny]=true; bool ok=true; FOR(it,key){ int kx=nx+it->F-r,ky=ny+it->S; if(kx<0 || kx>=d) continue; if(lock[kx][ky]=='#'){ ok=false; break; } } if(ok){ if(nx==cx) q.push(mp(nx,ny)); else nque.push(mp(nx,ny)); } } } q=nque; } cout<<"The key falls to depth "<<ans<<"."<<endl; } main(){ ios::sync_with_stdio(false); int t; cin>>t; rep(i,t) solve(); }