あけましておめでとうございます。私はひたすら AOJ-ICPC を埋めています。
実装が面倒だなあこれ・・・と思ったのでほぼ自分用記事を書きます。
問題概要
原文 → Amazing Mazes | Aizu Online Judge
縦 、横 の迷路が与えられる。迷路の壁の情報が与えられるので、スタートからゴールまでの最短距離を求めよ。ゴールに辿りつけない迷路の場合は を出力せよ。
解説
解法としてはもちろん幅優先探索なんですが、今回は迷路の「壁」が与えられるため少し面倒です。いつもの方針と少し違う配列を持つ必要があります。
board[i][j][k] := 座標(i, j) において方向 k に動けるか
という bool 配列を用意します。これさえ用意できればあとは普通に探索するだけです。が、バグが怖いですね。
ソースコード
int dx[]={1, -1, 0, 0}; int dy[]={0, 0, 1, -1}; signed main() { int h, w; while(cin >> w >> h, h || w) { bool board[40][40][4]; rep(i,0,h) rep(j,0,w) rep(k,0,4) board[i][j][k] = true; rep(i,0,h) board[i][0][3] = false; // left rep(i,0,h) board[i][w-1][2] = false; // right rep(i,0,w) board[0][i][1] = false; // up rep(i,0,w) board[h-1][i][0] = false; // down int inp; rep(i,0,2*h-1) { int l; if(i % 2 == 0) l = w-1; else l = w; rep(j,0,l) { cin >> inp; if(inp == 1) { if(i % 2 == 0) { board[i/2][j][2] = false; board[i/2][j+1][3] = false; } else { board[i/2][j][0] = false; board[i/2+1][j][1] = false; } } } } int dist[40][40]; rep(i,0,h) rep(j,0,w) dist[i][j] = INF; dist[0][0] = 1; queue<pii> q; q.push(pii(0, 0)); while(!q.empty()) { pii t = q.front(); q.pop(); rep(i,0,4) { if(!board[t.fr][t.sc][i]) continue; int x = t.fr + dx[i]; int y = t.sc + dy[i]; if(dist[x][y] <= dist[t.fr][t.sc] + 1) continue; dist[x][y] = dist[t.fr][t.sc] + 1; q.push(pii(x, y)); } } if(dist[h-1][w-1] == INF) cout << 0 << endl; else cout << dist[h-1][w-1] << endl; } return 0; }
なんか壁与えられる問題他にもあった気がする。