結果
問題 | No.424 立体迷路 |
ユーザー | taba |
提出日時 | 2024-08-02 17:54:27 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 3,799 bytes |
コンパイル時間 | 13,506 ms |
コンパイル使用メモリ | 390,436 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-02 17:54:43 |
合計ジャッジ時間 | 15,496 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,812 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,944 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 1 ms
6,944 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 1 ms
6,944 KB |
testcase_09 | AC | 1 ms
6,944 KB |
testcase_10 | AC | 1 ms
6,944 KB |
testcase_11 | AC | 1 ms
6,940 KB |
testcase_12 | AC | 1 ms
6,944 KB |
testcase_13 | AC | 1 ms
6,940 KB |
testcase_14 | AC | 1 ms
6,944 KB |
testcase_15 | AC | 1 ms
6,940 KB |
testcase_16 | AC | 1 ms
6,944 KB |
testcase_17 | AC | 2 ms
6,944 KB |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | AC | 2 ms
6,944 KB |
testcase_20 | AC | 1 ms
6,940 KB |
testcase_21 | AC | 1 ms
6,940 KB |
testcase_22 | AC | 1 ms
6,940 KB |
testcase_23 | AC | 1 ms
6,940 KB |
testcase_24 | AC | 3 ms
6,940 KB |
testcase_25 | AC | 2 ms
6,940 KB |
ソースコード
use std::collections::{HashMap, HashSet}; fn main() { proconio::input! { h: i64, w:i64, s: (i64, i64), g: (i64, i64), b: [String; h], } let s = (s.1 - 1, s.0 - 1); let g = (g.1 - 1, g.0 - 1); let b = b .into_iter() .map(|s| { s.chars() .map(|x| x.to_digit(10).unwrap() as i8) .collect::<Vec<_>>() }) .collect::<Vec<_>>(); let mut movable: HashMap<(i64, i64), Vec<(i64, i64)>> = HashMap::new(); // 横 for y in 0..h { for x in 0..w - 1 { if (b[y as usize][x as usize] - b[y as usize][x as usize + 1]).abs() <= 1 { if let Some(v) = movable.get_mut(&(x, y)) { v.push((x + 1, y)); } else { movable.insert((x, y), vec![(x + 1, y)]); } if let Some(v) = movable.get_mut(&(x + 1, y)) { v.push((x, y)); } else { movable.insert((x + 1, y), vec![(x, y)]); } } } } for y in 0..h { for x in 0..w - 2 { if b[y as usize][x as usize] == b[y as usize][x as usize + 2] && b[y as usize][x as usize] > b[y as usize][x as usize + 1] { if let Some(v) = movable.get_mut(&(x, y)) { v.push((x + 2, y)); } else { movable.insert((x, y), vec![(x + 2, y)]); } if let Some(v) = movable.get_mut(&(x + 2, y)) { v.push((x, y)); } else { movable.insert((x + 2, y), vec![(x, y)]); } } } } // 縦 for y in 0..h - 1 { for x in 0..w { if (b[y as usize][x as usize] - b[y as usize + 1][x as usize]).abs() <= 1 { if let Some(v) = movable.get_mut(&(x, y)) { v.push((x, y + 1)); } else { movable.insert((x, y), vec![(x, y + 1)]); } if let Some(v) = movable.get_mut(&(x, y + 1)) { v.push((x, y)); } else { movable.insert((x, y + 1), vec![(x, y)]); } } } } for y in 0..h - 2 { for x in 0..w { if b[y as usize][x as usize] == b[y as usize + 2][x as usize] && b[y as usize][x as usize] > b[y as usize + 1][x as usize] { if let Some(v) = movable.get_mut(&(x, y)) { v.push((x, y + 2)); } else { movable.insert((x, y), vec![(x, y + 2)]); } if let Some(v) = movable.get_mut(&(x, y + 2)) { v.push((x, y)); } else { movable.insert((x, y + 2), vec![(x, y)]); } } } } let mut from = HashSet::new(); let mut visited = HashSet::new(); from.insert(s); let goal = loop { let mut to = HashSet::new(); for from in from { if let Some(v) = movable.get(&from) { for t in v { if !visited.contains(t) { visited.insert(*t); to.insert(*t); } } } } // ゴールに到着したらtrue if to.contains(&g) { break true; } // 行ける場所がなくなったらfalse if to.is_empty() { break false; } from = to; }; if goal { println!("YES"); } else { println!("NO"); } }