hogecoder

tsutaj 競技プログラミングの記録

AOJ 0037: Path on a Grid

バグが取れなくて相当苦労した。

問題概要

原文 → 格子状の経路 | Aizu Online Judge

格子の各辺が壁であるかどうかの情報が与えられる。壁に右手をついたまま1周するときの経路を出力せよ。

解説

前回の記事 と同様の方法で解いてみました。

今見ている方向を  k とおくと、

  • 右手に壁がない場合、 (k+1) \% 4 の方向に向き直す
  • 進行方向に壁がある場合、 ( (k - 1 + 4) \% 4 の方向に向き直す

というように動けばよいです。終了条件にも気をつけましょう。

ソースコード

#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 使って書きなおしたほうがいいよなあ。