結果

問題 No.2928 Gridpath
ユーザー tnodinotnodino
提出日時 2024-10-05 17:25:39
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 1 ms
5,248 KB
testcase_12 AC 1 ms
5,248 KB
testcase_13 AC 1 ms
5,248 KB
testcase_14 AC 1 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 1 ms
5,248 KB
testcase_17 AC 1 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 1 ms
5,248 KB
testcase_20 AC 1 ms
5,248 KB
testcase_21 AC 1 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

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