【AOJ 1166】Amazing Maze

問題

Amazing Mazes | Aizu Online Judge

方針

入力フォーマットが特殊な問題. （ここを理解するのに時間を取られる）
与えられた入力からフィールドを生成して, それに対してBFSする.
BFSはいいとしてフィールドの生成めちゃくちゃ手こずった. kyuridenamidaさんのコードをパク参考にさせてもらいました.

ソース

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

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

#define rep(i,n) REP(i,0,n)
#define REP(i,a,n) for(int i = a ; i < (int)n ; i++)
#define INF 1000000000

typedef pair<int ,int> P;

void init(int w, int h){
  rep(i, 200){
    rep(j, 200){
      maze[i][j] = 1;
    }
  }

  REP(i, 1, 2*h){
    REP(j, 1, 2*w){
      maze[i][j] = 0;
    }
  }
}

signed main(){

  cin.tie(0);
  ios::sync_with_stdio(false);
  
  while(cin >> w >> h, w || h){
    init(w, h);
    
    int in;
    rep(i, 2*h-1){
      if(i%2 == 0){ // 縦
        rep(j, w-1){
          cin >> in;
          rep(k, 3){
            maze[i+k][2*j+2] |= in;
          }
        }
      }else{ // 横
        rep(j, w){
          cin >> in;
          rep(k, 3){
            maze[i+1][j*2+k] |= in;
          }
        }
      }      
    }
    
    queue<P> que;
    que.push(P(1, 1));

    rep(i, 200){
      rep(j, 200){
        d[i][j] = INF;
      }
    }

    d[1][1] = 1; 
    int ans = 0;
    while(!que.empty()){
      P p = que.front(); que.pop();

      if(p.first == 2*h-1 && p.second == 2*w-1){
        ans = (d[p.first][p.second]+2)/2; 
        break;
      } 

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

        if(maze[nx][ny] == 0 && d[nx][ny] == INF){
          que.push(P(nx, ny));
          d[nx][ny] = d[p.first][p.second] + 1;
        }
      }
    }
    cout << ans << endl;
  }
}

参考

kyuridenamida.hatenablog.com

思いついても上手いこと実装できなかったので, 練習の足りなさを感じる. がんばろう.