PKU : 3083 - Children of the Candy Corn

問題概要

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

周りが壁に囲まれた迷路が入力されます.
スタート地点とゴール地点は, 壁際に必ずあります.
このとき, スタート地点から, 左手法と右手法を使って何ステップでゴールにつけるか答えてください.
また, スタートからゴールまでの最短距離も答えてください.

アルゴリズム

左と右の壁ぞいに歩くのは, ただ実装するだけ.
スタートからゴールまでの最短距離は, BFSするだけ.

プログラム

typedef struct{
  int x,y,cost;
}P;

int w,h;
int sx,sy,gx,gy;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
char t[42][42];

int wall(int dir){
  int x = sx, y = sy;
  int d = (x==0 ? 1 : y==0 ? 2 : x==w-1 ? 3 : 0);
  int res = 1;

  while(x != gx || y != gy){
    int nd = (d + dir) % 4;
    int nx = x + dx[nd];
    int ny = y + dy[nd];
    int nx2 = x + dx[d];
    int ny2 = y + dy[d];

    if(t[ny][nx] == '.'){
      d = nd;
      x = nx;
      y = ny;
      res++;
    }
    else if(t[ny2][nx2] == '.'){
      x = nx2;
      y = ny2;
      res++;
    }
    else{
      d = (d + dir + 2) % 4;
    }
  }

  return res;
}

int shortest(){
  queue<P> open;
  bool closed[42][42];
  memset(closed,0,sizeof(closed));

  P p = {sx,sy,1};
  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){
      return p.cost;
    }

    rep(i,4){
      int nx = p.x + dx[i];
      int ny = p.y + dy[i];
      if(t[ny][nx] == '.'){
        P np = {nx,ny,p.cost+1};
        open.push(np);
      }
    }
  }

  return -1;
}

int main(void){
  int T;
  scanf("%d",&T);

  while(T--){
    scanf("%d%d",&w,&h);
    rep(i,h){
      scanf("%s",t[i]);
      rep(j,w){
        if(t[i][j] == 'S'){
          sx = j;
          sy = i;
          t[i][j] = '.';
        }
        else if(t[i][j] == 'E'){
          gx = j;
          gy = i;
          t[i][j] = '.';
        }
      }
    }

    printf("%d %d %d\n",wall(3),wall(1),shortest());
  }
}