結果
問題 | No.2411 Reverse Directions |
ユーザー | akakimidori |
提出日時 | 2023-08-11 22:46:32 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 4,510 bytes |
コンパイル時間 | 14,174 ms |
コンパイル使用メモリ | 393,128 KB |
実行使用メモリ | 16,768 KB |
最終ジャッジ日時 | 2024-04-29 13:54:23 |
合計ジャッジ時間 | 15,728 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 5 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 12 ms
14,080 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 17 ms
16,768 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 20 ms
11,648 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 6 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 7 ms
5,376 KB |
testcase_18 | AC | 3 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 6 ms
5,376 KB |
testcase_21 | AC | 8 ms
6,400 KB |
testcase_22 | AC | 14 ms
8,832 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 18 ms
10,880 KB |
testcase_25 | AC | 1 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 5 ms
5,376 KB |
testcase_28 | AC | 10 ms
7,680 KB |
testcase_29 | AC | 21 ms
12,160 KB |
testcase_30 | AC | 12 ms
8,704 KB |
testcase_31 | AC | 14 ms
7,936 KB |
コンパイルメッセージ
warning: unused variable: `w` --> src/main.rs:8:9 | 8 | w: usize, | ^ | help: `w` is captured in macro and introduced a unused variable --> src/main.rs:127:13 | 6 | / input! { 7 | | h: usize, 8 | | w: usize, 9 | | k: usize, ... | 12 | | s: [bytes; h], 13 | | } | |_____- in this macro invocation ... 127 | let $var = read_value!($iter, $t); | ^^^^ = note: `#[warn(unused_variables)]` on by default = note: this warning originates in the macro `input_inner` which comes from the expansion of the macro `input` (in Nightly builds, run with -Z macro-backtrace for more info)
ソースコード
use std::collections::*; type Deque<T> = VecDeque<T>; fn main() { input! { h: usize, w: usize, k: usize, l: usize, r: usize, s: [bytes; h], } if let Some(ans) = solve(k, l - 1, r, s) { println!("Yes"); println!("{}", ans); } else { println!("No"); } } fn solve(k: usize, l: usize, r: usize, s: Vec<Vec<u8>>) -> Option<String> { if (r - l) % 2 != 0 { return None; } let (h, w) = (s.len(), s[0].len()); let inf = std::usize::MAX / 2; let bfs = |x: usize, y: usize| -> Vec<Vec<(usize, (usize, usize))>> { let mut dp = vec![vec![(inf, (h, w)); w]; h]; dp[x][y] = (0, (x, y)); let mut deq = Deque::new(); deq.push_back((x, y)); while let Some((x, y)) = deq.pop_front() { let d = dp[x][y].0 + 1; let mut dir = (1, 0); for _ in 0..4 { let (x, y) = (x + dir.0, y + dir.1); if x < h && y < w && s[x][y] != b'#' && dp[x][y].0 > d { dp[x][y] = (d, (x - dir.0, y - dir.1)); deq.push_back((x, y)); } dir = (!dir.1 + 1, dir.0); } } dp }; let op = |src: (usize, usize), dst: (usize, usize)| -> char { if src.0 + 1 == dst.0 { 'D' } else if src.0 == dst.0 + 1 { 'U' } else if src.1 + 1 == dst.1 { 'R' } else { 'L' } }; let a = bfs(0, 0); let b = bfs(h - 1, w - 1); for i in 0..h { for j in 0..w { let p = a[i][j].0; let q = b[i][j].0; let mut cond = true; cond &= p <= l && (l - p) % 2 == 0; cond &= q <= k - r && (k - r - q) % 2 == 0; let ud = 1 <= i && i + 1 < h && s[i - 1][j] == b'.' && s[i + 1][j] == b'.'; let lr = 1 <= j && j + 1 < w && s[i][j - 1] == b'.' && s[i][j + 1] == b'.'; if cond && (ud || lr) { let mut ans = vec![]; let mut pos = (i, j); while pos != (0, 0) { let pre = a[pos.0][pos.1].1; ans.push(op(pre, pos)); pos = pre; } ans.reverse(); if lr { for _ in 0..((r - p + (k - r - q)) / 2) { ans.push('L'); ans.push('R'); } } else { for _ in 0..((r - p + (k - r - q)) / 2) { ans.push('U'); ans.push('D'); } } let mut pos = (i, j); while pos != (h - 1, w - 1) { let next = b[pos.0][pos.1].1; ans.push(op(pos, next)); pos = next; } return Some(ans.into_iter().collect()); } } } None } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::<Vec<char>>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::<Vec<u8>>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ----------