PKU : 2935 - Basic Wall Maze

問題概要

http://poj.org/problem?id=2935

6*6の格子状のマップがあります.
長さが１〜６の壁が３つだけあり, 壁を乗り越えることはできなくなっています.
スタート地点からゴール地点までの最短経路を出力せよ.

アルゴリズム

{x座標, y座標, 経路情報} を保持して幅優先すれば解ける.
マップ作成が少し面倒なだけ.
マップ情報は, それぞれのマスの上下左右に壁があるかないかのフラグで管理しています.

プログラム

struct Wall{
  bool flg[4];
}t[6][6];

typedef struct{
  int x,y;
  string s;
}P;

int sx,sy,gx,gy;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
string dir[] = {"N","E","S","W"};

void solve(){
  queue<P> open;
  bool closed[6][6];
  memset(closed,0,sizeof(closed));

  P p = {sx,sy,""};

  open.push(p);

  while(!open.empty()){
    p = open.front(); open.pop();
    if(closed[p.x][p.y]) continue;
    closed[p.x][p.y] = true;

    if(p.x == gx && p.y == gy){
      printf("%s\n",p.s.c_str());
      return;
    }

    rep(i,4){
      int nx = p.x + dx[i];
      int ny = p.y + dy[i];

      if(nx>=0 && 6>nx && ny>=0 && 6>ny && !t[p.y][p.x].flg[i]){
        P np = {nx,ny,p.s+dir[i]};
        open.push(np);
      }
    }
  }
}

int main(void){
  while(scanf("%d%d",&sx,&sy),sx||sy){
    scanf("%d%d",&gx,&gy);
    sx--;sy--;gx--;gy--;
    memset(t,0,sizeof(t));

    rep(i,3){
      int fx,fy,tx,ty;
      scanf("%d%d%d%d",&fx,&fy,&tx,&ty);

      if(fx == tx){
        REP(i,fy,ty){
          if(fx - 1 >= 0){
            t[i][fx-1].flg[1] = true;
          }
          if(fx < 6){
            t[i][fx].flg[3] = true;
          }
        }
      }
      else{
        REP(j,fx,tx){
          if(fy - 1 >= 0){
            t[fy-1][j].flg[2] = true;
          }
          if(fy < 6){
            t[fy][j].flg[0] = true;
          }
        }
      }
    }

    solve();
  }
}