use std::collections::*; type Deque = VecDeque; 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>) -> Option { 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> { 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::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ----------