結果

問題 No.2928 Gridpath
ユーザー tnodino
提出日時 2024-10-05 17:25:39
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,519 bytes
コンパイル時間 13,152 ms
コンパイル使用メモリ 379,600 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 08:47:14
合計ジャッジ時間 13,552 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #

use proconio::input;
use proconio::fastout;
use proconio::marker::Usize1;

const DX: &[usize] = &[!0, 1, 0, 0];
const DY: &[usize] = &[ 0, 0,!0, 1];

#[allow(non_snake_case)]
fn dfs(x: usize, y: usize, Gi: usize, Gj: usize, H: usize, W: usize, flg: &mut Vec<Vec<bool>>) -> usize {
    if Gi == x && Gj == y {
        return 1;
    }
    let mut ret = 0;
    for d in 0..4 {
        let nx = x.wrapping_add(DX[d]);
        let ny = y.wrapping_add(DY[d]);
        if nx >= H || ny >= W {
            continue;
        }
        if flg[nx][ny] {
            continue;
        }
        let mut cnt = 0;
        for d in 0..4 {
            let mx = nx.wrapping_add(DX[d]);
            let my = ny.wrapping_add(DY[d]);
            if mx >= H || my >= W {
                continue;
            }
            if flg[mx][my] {
                cnt += 1;
            }
        }
        if cnt == 1 {
            flg[nx][ny] = true;
            ret += dfs(nx, ny, Gi, Gj, H, W, flg);
            flg[nx][ny] = false;
        }
    }
    return ret;
}

#[fastout]
#[allow(non_snake_case)]
fn main() {
    input! {
        (H, W): (usize, usize),
        (Si, Sj): (Usize1, Usize1),
        (Gi, Gj): (Usize1, Usize1),
    }
    assert!(1 <= H && H <= 6);
    assert!(1 <= W && W <= 6);
    assert!(Si < H);
    assert!(Gi < H);
    assert!(Sj < W);
    assert!(Gj < W);
    assert!(Si != Gi || Sj != Gj);
    let mut flg = vec![vec![false; W]; H];
    flg[Si][Sj] = true;
    println!("{}", dfs(Si, Sj, Gi, Gj, H, W, &mut flg));
}
0