dp 파이프 이동 1

#[allow(clippy::all)]
#[allow(unused_must_use, unused_doc_comments)]
fn solve<R: BufRead, W: Write>(io: &mut IO<R, W>) -> Option<()> {
    let n = io.get(0usize)?;
    let grid = io.get(vec![vec![0usize; n]; n])?;

    // 0 - horizontal, 1 - vertical, 2 - diagonal
    // dp[i][j][파이프상태] = 경우의 수
    let mut dp = vec![vec![vec![0usize; 3]; n]; n];

    // 초기 상태: (0, 1)에 horizontal 파이프
    dp[0][1][0] = 1;

    for i in 0..n {
        for j in 0..n {
            if grid[i][j] == 1 { continue; } // 벽인 경우 건너뛰기

            // 현재 위치에서 가능한 각 상태에 대해
            for state in 0..3 {
                if dp[i][j][state] == 0 { continue; }

                // 다음 가능한 이동들 계산
                let moves = get_possible_moves(&grid, i, j, n, state);

                for PipeState(next_state, ny, nx) in moves {
                    dp[ny][nx][next_state] += dp[i][j][state];
                }
            }
        }
    }

    // 목표 지점 (n-1, n-1)에 도달하는 모든 경우의 수 합산
    let result = dp[n - 1][n - 1][0] + dp[n - 1][n - 1][1] + dp[n - 1][n - 1][2];
    io.put(result).nl();

    None
}

struct PipeState(usize, usize, usize);  // (state, y, x)

fn get_possible_moves(
    grid: &[Vec<usize>],
    y: usize,
    x: usize,
    max_size: usize,
    current_state: usize,
) -> Vec<PipeState> {
    let mut moves = Vec::new();

    let right = x + 1 < max_size && grid[y][x + 1] == 0;
    let down = y + 1 < max_size && grid[y + 1][x] == 0;
    let diag = x + 1 < max_size && y + 1 < max_size &&
        grid[y][x + 1] == 0 && grid[y + 1][x] == 0 && grid[y + 1][x + 1] == 0;

    // 수평 이동 (현재가 수평 또는 대각선일 때)
    if right && (current_state == 0 || current_state == 2) {
        moves.push(PipeState(0, y, x + 1));
    }

    // 수직 이동 (현재가 수직 또는 대각선일 때)
    if down && (current_state == 1 || current_state == 2) {
        moves.push(PipeState(1, y + 1, x));
    }

    // 대각선 이동 (모든 상태에서 가능)
    if diag {
        moves.push(PipeState(2, y + 1, x + 1));
    }

    moves
}