PKU 3083 Children of the Candy Corn

http://poj.org/problem?id=3083
迷路が与えられる。
スタートからゴールまで壁に手をついてゴールを目指した場合を左の壁、右の壁の場合について何マス通るかと、最短経路が何マスなのかを答えるというような問題。

完全な実装探索ゲー。
左右をやるのは一つのループを使いまわしました。

string in[40];

main(){
  int T;
  cin>>T;
  while(T--){
    int h,w;
    cin>>w>>h;
    int sx,sy,sd;
    rep(i,h){
      cin>>in[i];
      rep(j,w)if(in[i][j]=='S'){
        sx=i,sy=j;
        if(i==0)sd=1;
        if(i==h-1)sd=3;
        if(j==0)sd=0;
        if(j==w-1)sd=2;
      }
    }

    rep(i,2){
      int cx=sx,cy=sy,cd=sd;
      int mi=1;
      if(i)mi=-1;
      int ti=0;
      int step=0;
      while(true){
        ++step;
        if(in[cx][cy]=='E')break;
        rep(j,4){
          int nx=cx+dx[(cd+mi*j+2+mi+8)%4],ny=cy+dy[(cd+mi*j+2+mi+8)%4];
          if(in[nx][ny]=='#')continue;
          cx=nx,cy=ny;
          cd=(cd+mi*j+2+mi+8)%4;
          break;
        }
      }
      cout<<step<<' ';
    }
    queue<pair<PI,int> >q;
    q.push(mp(mp(sx,sy),0));
    bool vis[h][w];
    memset(vis,0,sizeof(vis));
    while(!q.empty()){
      int cx=q.front().F.F,cy=q.front().F.S,co=q.front().S;
      q.pop();
      if(vis[cx][cy])continue;
      vis[cx][cy]=true;
      if(in[cx][cy]=='E'){
        cout<<co+1<<endl;
        break;
      }
      rep(i,4){
        int nx=cx+dx[i],ny=cy+dy[i];
        if(nx<0 || h<=nx ||
           ny<0 || w<=ny ||
           vis[nx][ny] || in[nx][ny]=='#')continue;
        q.push(mp(mp(nx,ny),co+1));
      }
    }
  }
}