バグが取れなくて相当苦労した。
問題概要
原文 → 格子状の経路 | Aizu Online Judge
格子の各辺が壁であるかどうかの情報が与えられる。壁に右手をついたまま1周するときの経路を出力せよ。
解説
前回の記事 と同様の方法で解いてみました。
今見ている方向を とおくと、
- 右手に壁がない場合、 の方向に向き直す
- 進行方向に壁がある場合、 の方向に向き直す
というように動けばよいです。終了条件にも気をつけましょう。
ソースコード
#define S 6 // right, down, left, up int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; int main() { bool board[S][S][4] = {}; rep(i,0,9) { int l, n; if(i % 2 == 0) l = 4; else l = 5; rep(j,0,l) { scanf("%1d", &n); if(n == 1) { if(i % 2 == 0) { board[i/2][j+1][1] = true; board[i/2+1][j+1][3] = true; } else { board[i/2+1][j][0] = true; board[i/2+1][j+1][2] = true; } } } } string d = "RDLU"; string ret; int dir = 0; int nx = 0, ny = 1; for(int i=0; i<150; i++) { if(nx == 1 && ny == 0 && dir == 2) break; if(nx == 0 && ny == 0 && dir == 3) break; int x, y; x = nx + dx[dir], y = ny + dy[dir]; if(board[nx][ny][(dir + 1) % 4] == 0) { dir = (dir + 1) % 4; nx = nx + dx[dir], ny = ny + dy[dir]; } else if(board[nx][ny][dir] == 1) { ret += d[dir]; dir = (dir - 1 + 4) % 4; } else { ret += d[dir]; nx = x, ny = y; } } cout << ret << endl; return 0; }
自分の実装の方法が悪いのか、バグ直しに相当時間がかかってしまった・・・。他の実装方法も考えたい。まずは enum 使って書きなおしたほうがいいよなあ。