結果

問題 No.3121 Prime Dance
ユーザー magurofly
提出日時 2025-04-19 13:16:46
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 2,090 bytes
コンパイル時間 13,883 ms
コンパイル使用メモリ 403,096 KB
実行使用メモリ 40,832 KB
最終ジャッジ日時 2025-04-19 13:17:13
合計ジャッジ時間 27,081 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 8 WA * 12 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::{HashSet, VecDeque};

use proconio::{input, marker::{Chars, Usize1}};

fn main() {
    let primes = [2_u32, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199].into_iter().collect::<HashSet<_>>();

    input! {
        h: usize, w: usize,
        sx: Usize1, sy: Usize1,
        gx: Usize1, gy: Usize1,
        c: [Chars; h],
    }

    let mut grid = vec![vec![HashSet::new(); w]; h];
    grid[sx][sy].insert(0);
    let mut queue = VecDeque::new();
    queue.push_back((sx, sy, [0; 4]));
    while let Some((i, j, ds)) = queue.pop_front() {
        // if (i, j) == (gx, gy) && ds.iter().all(|d| primes.contains(d) ) {
        //     break;
        // }
        let mut next = |i2: usize, j2: usize, ds2: [_; 4]| {
            let hash = (ds2[0] as u32) << 24 | (ds2[1] as u32) << 16 | (ds2[2] as u32) << 8 | ds2[3] as u32;
            let sum = (ds2[0] as u32) + (ds2[1] as u32) + (ds2[2] as u32) + (ds2[3] as u32);
            if c[i2][j2] != '#' && sum < 300 && grid[i2][j2].insert(hash) {
                queue.push_back((i2, j2, ds2));
            }
        };
        if i > 0 {
            let mut ds2 = ds;
            ds2[0] += 1;
            next(i - 1, j, ds2)
        }
        if i + 1 < h {
            let mut ds2 = ds;
            ds2[1] += 1;
            next(i + 1, j, ds2)
        }
        if j > 0 {
            let mut d2 = ds;
            d2[2] += 1;
            next(i, j - 1, d2)
        }
        if j + 1 < w {
            let mut d2 = ds;
            d2[3] += 1;
            next(i, j + 1, d2)
        }
    }

    let mut ans = 1_000_000_000;
    // eprintln!("{:?}", grid[gx][gy]);
    for ds in &grid[gx][gy] {
        let ds = [ds >> 24, ds >> 16 & 0xff, ds >> 8 & 0xff, ds & 0xff];
        if !ds.iter().all(|d| primes.contains(d) ) {
            continue;
        }
        let sum = ds.iter().map(|&d| d as u32 ).sum::<u32>();
        ans = ans.min(sum);
    }
    println!("{ans}");
}
0