AOJ : 2132 - Left Hand Rule

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2132
迷路の壁情報と, スタート位置・ゴール位置が与えられる.
左手法によりゴールまで辿りつけるならば, 歩数を出力.
辿りつけないならば, Impossibleと出力.

スタート位置は, 一番外側の壁のどこかにあると仮定してよい.
ゴール位置は, マス目のどこかを示している.

アルゴリズム

ひたすら実装です.
迷路のデータ構造は, 「各マスの上下左右に壁があるかないか」を管理する方法で作りました.
迷路を辿るときは, bool used[ 102 (x座標) ][ 102 (y座標) ][ 4 (方向) ] というclosedリスト的なものを作って, 同じ状態に２回以上なったらImpossibleとするようにしました.

プログラム

struct P{
  bool wall[4];
}t[200][200];

int w,h,n;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};

int main(void){
  while(scanf("%d%d%d",&w,&h,&n),w||h||n){
    /* 壁入力 */
    memset(t,0,sizeof(t));
    rep(i,h) t[i][0].wall[3] = t[i][w-1].wall[1] = true;
    rep(j,w) t[0][j].wall[0] = t[h-1][j].wall[2] = true;

    rep(i,n){
      int fx,fy,tx,ty;
      scanf("%d%d%d%d",&fx,&fy,&tx,&ty);
      if(fx > tx) swap(fx,tx);
      if(fy > ty) swap(fy,ty);

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

    /* スタート位置の情報を, マスとして考えた座標に置き換える */
    int x1,y1,x2,y2,gx,gy;
    scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&gx,&gy);

    if(x1 > x2) swap(x1,x2);
    if(y1 > y2) swap(y1,y2);

    int x=x1,y=y1,d=0;
    if(x1 == x2){
      if(x1 == 0){
        d = 1;
      }
      else{
        d = 3;
        x--;
      }
    }
    else{
      if(y1 == 0){
        d = 2;
      }
      else{
        d = 0;
        y--;
      }
    }

    /* 迷路辿り */
    int res = 1;
    bool flg = true; //ゴールできたかどうか
    bool used[102][102][4]; //closedリスト的なやつ
    memset(used,0,sizeof(used));

    while(x != gx || y != gy){
      //(x,y)の位置に方向dで来たことがあるならImpossible
      if(used[x][y][d]){
        flg = false;
        break;
      }
      used[x][y][d] = true;

      //左向いて空いてたらそっちいく
      if(!t[y][x].wall[(d+1)%4]){
        d = (d+1)%4;
        x += dx[d];
        y += dy[d];
        res++;
      }
      //前向いて空いてたらそっちいく
      else if(!t[y][x].wall[d]){
        x += dx[d];
        y += dy[d];
        res++;
      }
      //右向く
      else{
        d = (d + 3) % 4;
      }
    }

    if(flg){
      printf("%d\n",res);
    }
    else{
      printf("Impossible\n");
    }
  }
}