結果
問題 |
No.3121 Prime Dance
|
ユーザー |
![]() |
提出日時 | 2025-05-10 03:14:13 |
言語 | Rust (1.83.0 + proconio) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,224 bytes |
コンパイル時間 | 23,367 ms |
コンパイル使用メモリ | 400,184 KB |
実行使用メモリ | 476,584 KB |
最終ジャッジ日時 | 2025-05-10 03:14:47 |
合計ジャッジ時間 | 21,811 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 2 |
other | AC * 10 TLE * 1 -- * 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 = 400; let mut visited = vec![vec![vec![vec![false; w]; h]; C]; C]; let mut q = VecDeque::new(); q.push_back((0usize, 0usize, sx, sy, 0usize)); // (left, down, x, y, steps) visited[0][0][sx][sy] = true; let mut ans = usize::MAX; while let Some((left, down, x, y, steps)) = q.pop_front() { if x == gx && y == gy { 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 left < primes.len() && down < primes.len() && right < primes.len() && up < primes.len() && primes[left] && primes[down] && primes[right] && primes[up] { ans = ans.min(steps); } } // Move up if x > 0 && left + 1 < C && map[x - 1][y] != '#' && !visited[left + 1][down][x - 1][y] { visited[left + 1][down][x - 1][y] = true; q.push_back((left + 1, down, x - 1, y, steps + 1)); } // Move left if y > 0 && down + 1 < C && map[x][y - 1] != '#' && !visited[left][down + 1][x][y - 1] { visited[left][down + 1][x][y - 1] = true; q.push_back((left, down + 1, x, y - 1, steps + 1)); } // Move down if x + 1 < h && map[x + 1][y] != '#' && !visited[left][down][x + 1][y] { visited[left][down][x + 1][y] = true; q.push_back((left, down, x + 1, y, steps + 1)); } // Move right if y + 1 < w && map[x][y + 1] != '#' && !visited[left][down][x][y + 1] { visited[left][down][x][y + 1] = true; q.push_back((left, down, x, y + 1, steps + 1)); } } if ans == usize::MAX { println!("-1"); } else { println!("{}", ans); } }