壁の持ち方

AHC052 や AHC023 のように、グリッドのマスの間に壁があるような問題について。

壁の情報は bool wall[H][W][4] として、wall[y][x][dir] が「マス (y,x) から dir 方向に壁がある」を表すようにすると扱いやすいです。

グリッドの外に出れない制約も、wall[0][x][UP] = true などのようにグリッドの最も外側のマスから外に向かう方向に壁があるとすることで自然に表現できます。

Rustでの実装例

const N: usize = 30;
const UP: usize = 0;
const RIGHT: usize = 1;
const DOWN: usize = 2;
const LEFT: usize = 3;

struct Input {
    wall: [[[bool; 4]; N]; N],
}

impl Input {
    fn new() -> Input {
        let mut sc = scanner();
        let mut wall = [[[false; 4]; N]; N];
        // vertical
        for i in 0..N {
            let row = sc.next_str().unwrap();
            for j in 0..N - 1 {
                if row.chars().nth(j).unwrap() == '1' {
                    wall[i][j][RIGHT] = true;
                    wall[i][j + 1][LEFT] = true;
                }
            }
        }
        // horizontal
        for i in 0..N - 1 {
            let row = sc.next_str().unwrap();
            for j in 0..N {
                if row.chars().nth(j).unwrap() == '1' {
                    wall[i][j][DOWN] = true;
                    wall[i + 1][j][UP] = true;
                }
            }
        }
        // 外周
        for i in 0..N {
            wall[0][i][UP] = true;
            wall[N - 1][i][DOWN] = true;
            wall[i][0][LEFT] = true;
            wall[i][N - 1][RIGHT] = true;
        }
        Input { wall }
    }
}

【追記】

graph[i][j][dir]を「(i, j)からdir方向に移動したときにどのマスに行くか（壁に当たる場合は(i, j)のまま）」って定義したり

たしかにこの形式は便利そう