PKU 2935 Basic Wall Maze

http://poj.org/problem?id=2935
迷路の最短経路を出力する問題。

壁の処理が面倒くさい。
去年のICPCの国内予選問題のやつより少し難易度高い気がします。

int cost[20][20];
bool wa[20][20];

main(){
  int sx,sy,ex,ey;
  while(cin>>sx>>sy,sx|sy){
    cin>>ex>>ey;
    --sx,--sy,--ex,--ey;
    memset(cost,0,sizeof(cost));
    memset(wa,0,sizeof(wa));

    rep(i,3){
      int ksx,ksy,kex,key;
      cin>>ksx>>ksy>>kex>>key;
      if(ksx==kex){
        for(int y=ksy;y<key;y++)wa[ksx*2][y]=1;
      }else{
        for(int x=ksx*2+1;x<kex*2;x+=2)wa[x][key]=1;
      }
    }

    queue<pair<int,PI> > q;
    q.push(mp(1,mp(sx,sy)));

    while(!q.empty()){
      int cc=q.front().F,cx=q.front().S.F,cy=q.front().S.S;
      q.pop();
      if(cost[cx][cy])continue;
      cost[cx][cy]=cc;
      rep(i,4){
        int nx=cx+dx[i],ny=cy+dy[i];
        if(nx<0 || 6<=nx ||
           ny<0 || 6<=ny ||
           cost[nx][ny])continue;
        if(nx==cx){
          if(wa[2*nx+1][(ny+cy)/2+1])continue;
          q.push(mp(cc+1,mp(nx,ny)));
        }else{
          if(wa[(nx+cx)+1][ny])continue;
          q.push(mp(cc+1,mp(nx,ny)));
        }
      }
    }



    string out;
    int cx=ex,cy=ey;

    string dir="NWSE";
    while(cx!=sx || cy!=sy){

      rep(i,4){
        int nx=cx+dx[i],ny=cy+dy[i];
        if(nx<0 || 6<=nx ||
           ny<0 || 6<=ny ||
           cost[nx][ny]+1!=cost[cx][cy])continue;
        if(nx==cx){
          if(wa[2*nx+1][(ny+cy)/2+1])continue;
          out+=dir[i];
          cx=nx;
          cy=ny;
          break;
        }else{
          if(wa[(nx+cx)+1][ny])continue;
          out+=dir[i];
          cx=nx;
          cy=ny;
          break;
        }        
      }
    }
    reverse(ALL(out));
    cout<<out<<endl;
  }
}