結果
問題 |
No.3121 Prime Dance
|
ユーザー |
![]() |
提出日時 | 2025-05-10 03:09:27 |
言語 | Rust (1.83.0 + proconio) |
結果 |
MLE
|
実行時間 | - |
コード長 | 3,179 bytes |
コンパイル時間 | 16,054 ms |
コンパイル使用メモリ | 394,948 KB |
実行使用メモリ | 720,804 KB |
最終ジャッジ日時 | 2025-05-10 03:09:54 |
合計ジャッジ時間 | 23,703 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 2 |
other | AC * 6 MLE * 5 -- * 10 |
ソースコード
use std::collections::VecDeque; use std::io::{self, BufRead}; fn sieve(x: usize) -> Vec<bool> { let mut is_prime = vec![true; x + 1]; is_prime[0] = false; is_prime[1] = false; for i in 2..=x { if is_prime[i] { let mut j = i * 2; while j <= x { is_prime[j] = false; j += i; } } } is_prime } fn main() { let stdin = io::stdin(); let mut lines = stdin.lock().lines().map(|l| l.unwrap()); let prime_limit = 200000; let primes = sieve(prime_limit); let (h, w): (usize, usize) = { let v: Vec<usize> = lines .next() .unwrap() .split_whitespace() .map(|s| s.parse().unwrap()) .collect(); (v[0], v[1]) }; let (sx, sy): (usize, usize) = { let v: Vec<usize> = lines .next() .unwrap() .split_whitespace() .map(|s| s.parse::<usize>().unwrap() - 1) .collect(); (v[0], v[1]) }; let (gx, gy): (usize, usize) = { let v: Vec<usize> = lines .next() .unwrap() .split_whitespace() .map(|s| s.parse::<usize>().unwrap() - 1) .collect(); (v[0], v[1]) }; let map: Vec<Vec<char>> = (0..h).map(|_| lines.next().unwrap().chars().collect()).collect(); const C: usize = 300; let inf = 1 << 30; let mut dp = vec![vec![vec![vec![inf; w]; h]; C]; C]; let mut q = VecDeque::new(); q.push_back((0usize, 0usize, sx, sy)); dp[0][0][sx][sy] = 0; while let Some((left, down, x, y)) = q.pop_front() { let now = dp[left][down][x][y]; if x > 0 && left + 1 < C && map[x - 1][y] != '#' && dp[left + 1][down][x - 1][y] > now + 1 { dp[left + 1][down][x - 1][y] = now + 1; q.push_back((left + 1, down, x - 1, y)); } if y > 0 && down + 1 < C && map[x][y - 1] != '#' && dp[left][down + 1][x][y - 1] > now + 1 { dp[left][down + 1][x][y - 1] = now + 1; q.push_back((left, down + 1, x, y - 1)); } if x + 1 < h && map[x + 1][y] != '#' && dp[left][down][x + 1][y] > now + 1 { dp[left][down][x + 1][y] = now + 1; q.push_back((left, down, x + 1, y)); } if y + 1 < w && map[x][y + 1] != '#' && dp[left][down][x][y + 1] > now + 1 { dp[left][down][x][y + 1] = now + 1; q.push_back((left, down, x, y + 1)); } } let mut ans = inf; for i in 0..C { for j in 0..C { let count = dp[i][j][gx][gy]; if count >= inf { continue; } let left = i; let down = j; let right = (gx as isize - sx as isize + left as isize) as usize; let up = (gy as isize - sy as isize + down as isize) as usize; if primes[left] && primes[down] && primes[right] && primes[up] { ans = ans.min(count); } } } if ans > 1_000_000_000 { println!("-1"); } else { println!("{}", ans); } }