読者です 読者をやめる 読者になる 読者になる

AOJ 1166 Amazing Mazes

C/C++ AOJ BFS

問題

Amazing Mazes

解法

寝落ちして、1時ぐらいに解いた。一発AC。 BFSで解けます。下か上に行く時はin[y*2±1][x]が1なら進めない。左右はin[y*2][x]が1なら進めないってやっていく。

コード

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

int main(){
  while(scanf("%d%d", &w, &h) && w+h){
    rep(i, 2*h-1){
      rep(j, (i%2)?w:w-1) scanf("%d", &maze[i][j]);
    }

    map<pi, int>m;
    queue<pi>q;
    q.push(MP(0, 0));
    m[MP(0, 0)] = 1;
    int res = 1;
    while(!q.empty()){
      int qsize = (int)q.size();
      rep(i, qsize){
    pi now = q.front(); q.pop();
    rep(d, 4){
      int ny = now.Y + dy[d], nx = now.X + dx[d];
      if(ny < 0 || nx < 0 || ny >= h || nx >= w || m.count(MP(ny,nx))) continue;
      if(d == 0){
        if(maze[now.Y*2][now.X-1]) continue;
      }else if(d == 1){
        if(maze[now.Y*2-1][now.X]) continue;
      }else if(d == 2){
        if(maze[now.Y*2][now.X]) continue;
      }else if(d == 3){
        if(maze[now.Y*2+1][now.X]) continue;
      }

      m[MP(ny, nx)] = 1;
      q.push(MP(ny, nx));
      if(ny == h-1 && nx == w-1){
        printf("%d\n", res+1);
        goto e;
      }
    }
      }
      res++;
    }
    puts("0");
  e:;
  }
  return 0;
}

dのループのところは三項演算子とかでもっときれいにかけるし、 フォーマットといじってやると楽に出来たりするらしい