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();
}