結果

問題 No.2928 Gridpath
ユーザー naut3
提出日時 2024-10-14 19:46:45
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,162 bytes
コンパイル時間 13,488 ms
コンパイル使用メモリ 378,668 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-14 19:47:06
合計ジャッジ時間 14,630 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(non_snake_case, unused_must_use, unused_imports)]
use std::io::{self, prelude::*};

fn main() {
    let (stdin, stdout) = (io::read_to_string(io::stdin()).unwrap(), io::stdout());
    let (mut stdin, mut buffer) = (stdin.split_whitespace(), io::BufWriter::new(stdout.lock()));
    macro_rules! input {
        ($t: ty, $n: expr) => {
            (0..$n).map(|_| input!($t)).collect::<Vec<_>>()
        };
        ($t: ty) => {
            stdin.next().unwrap().parse::<$t>().unwrap()
        };
    }

    let H = input!(usize);
    let W = input!(usize);
    let sy = input!(usize) - 1;
    let sx = input!(usize) - 1;
    let ty = input!(usize) - 1;
    let tx = input!(usize) - 1;

    let mut cnt = 0;
    let mut seen = vec![vec![false; W]; H];
    seen[sy][sx] = true;

    dfs(
        H,
        W,
        sy,
        sx,
        ty,
        tx,
        &mut seen,
        sy,
        sx,
        &mut cnt,
    );

    writeln!(buffer, "{}", cnt);
}

fn dfs(
    H: usize,
    W: usize,
    sy: usize,
    sx: usize,
    ty: usize,
    tx: usize,
    seen: &mut Vec<Vec<bool>>,
    ny: usize,
    nx: usize,
    cnt: &mut usize,
) -> () {
    if ny == ty && nx == tx {
        *cnt += 1;
    }

    if ny > 0 && !seen[ny - 1][nx] {
        let mut isok = true;

        if ny >= 2 && seen[ny - 2][nx] {
            isok = false;
        }

        if nx >= 1 && seen[ny - 1][nx - 1] {
            isok = false;
        }

        if nx + 1 < W && seen[ny - 1][nx + 1] {
            isok = false;
        }

        if isok {
            seen[ny - 1][nx] = true;
            dfs(H, W, sy, sx, ty, tx, seen, ny - 1, nx, cnt);
            seen[ny - 1][nx] = false;
        }
    }

    if ny + 1 < H && !seen[ny + 1][nx] {
        let mut isok = true;

        if ny + 2 < H && seen[ny + 2][nx] {
            isok = false;
        }

        if nx >= 1 && seen[ny + 1][nx - 1] {
            isok = false;
        }

        if nx + 1 < W && seen[ny + 1][nx + 1] {
            isok = false;
        }

        if isok {
            seen[ny + 1][nx] = true;
            dfs(H, W, sy, sx, ty, tx, seen, ny + 1, nx, cnt);
            seen[ny + 1][nx] = false;
        }
    }

    if nx > 0 && !seen[ny][nx - 1] {
        let mut isok = true;

        if nx >= 2 && seen[ny][nx - 2] {
            isok = false;
        }

        if ny > 0 && seen[ny - 1][nx - 1] {
            isok = false;
        }

        if ny + 1 < H && seen[ny + 1][nx - 1] {
            isok = false;
        }

        if isok {
            seen[ny][nx - 1] = true;
            dfs(H, W, sy, sx, ty, tx, seen, ny, nx - 1, cnt);
            seen[ny][nx - 1] = false;
        }
    }

    if nx + 1 < W && !seen[ny][nx + 1] {
        let mut isok = true;

        if nx + 2 < W && seen[ny][nx + 2] {
            isok = false;
        }

        if ny > 0 && seen[ny - 1][nx + 1] {
            isok = false;
        }

        if ny + 1 < H && seen[ny + 1][nx + 1] {
            isok = false;
        }

        if isok {
            seen[ny][nx + 1] = true;
            dfs(H, W, sy, sx, ty, tx, seen, ny, nx + 1, cnt);
            seen[ny][nx + 1] = false;
        }
    }
}
0