use std::{cmp::Reverse, collections::BinaryHeap}; use proconio::{input, marker::Chars}; fn main() { input! { h:usize, w:usize, s:[Chars;h], } const INF: usize = std::usize::MAX; let mut dists = vec![vec![(INF, 0usize); w]; h]; dists[0][0] = (0, 0); let mut pq = BinaryHeap::new(); pq.push(Reverse((0, 0, 0))); while let Some(Reverse((yoko, tate, crr))) = pq.pop() { let (cx, cy) = (crr / w, crr % w); if dists[cx][cy] < (yoko, tate) { continue; } for Pos { x: nx, y: ny } in Pos::new(cx, cy).neigh4(h, w) { if s[nx][ny] == '#' { continue; } let dist_nxt = if cx == nx { (dists[cx][cy].0 + 1, dists[cx][cy].1) } else { (dists[cx][cy].0, dists[cx][cy].1 + 1) }; if dist_nxt < dists[nx][ny] { dists[nx][ny] = dist_nxt; pq.push(Reverse((dist_nxt.0, dist_nxt.1, nx * w + ny))); } } } if dists[h - 1][w - 1] == (INF, 0) { println!("No"); } else { let (ans_x, ans_y) = dists[h - 1][w - 1]; println!("Yes"); println!("{} {}", ans_x, ans_y); } } use grid_mgr::*; mod grid_mgr { //[R,D,L,U] pub const DIR4: [(usize, usize); 4] = [(0, 1), (1, 0), (0, !0), (!0, 0)]; pub const DIR8: [(usize, usize); 8] = [ (1, 0), (1, !0), (0, !0), (!0, !0), (!0, 0), (!0, 1), (0, 1), (1, 1), ]; pub struct Pos { pub x: usize, pub y: usize, } impl Pos { #[allow(dead_code)] pub fn new(x: usize, y: usize) -> Self { Self { x, y } } #[allow(dead_code)] pub fn neigh4<'a>(&'a self, h: usize, w: usize) -> impl Iterator + 'a { DIR4.iter().filter_map(move |&(dx, dy)| { let nx = self.x.wrapping_add(dx); let ny = self.y.wrapping_add(dy); if nx < h && ny < w { Some(Pos::new(nx, ny)) } else { None } }) } #[allow(dead_code)] pub fn neigh8<'a>(&'a self, h: usize, w: usize) -> impl Iterator + 'a { DIR8.iter().filter_map(move |&(dx, dy)| { let nx = self.x.wrapping_add(dx); let ny = self.y.wrapping_add(dy); if nx < h && ny < w { Some(Pos::new(nx, ny)) } else { None } }) } #[allow(dead_code)] pub fn line<'a>( &'a self, h: usize, w: usize, dir: (usize, usize), ) -> impl Iterator + 'a { (0..).map_while(move |i| { let nx = self.x.wrapping_add(dir.0.wrapping_mul(i)); let ny = self.y.wrapping_add(dir.1.wrapping_mul(i)); if nx < h && ny < w { Some(Pos::new(nx, ny)) } else { None } }) } #[allow(dead_code)] pub fn _moveto(&self, h: usize, w: usize, dir: (usize, usize)) -> Option { let nx = self.x.wrapping_add(dir.0); let ny = self.y.wrapping_add(dir.1); if nx < h && ny < w { Some(Pos::new(nx, ny)) } else { None } } #[allow(dead_code)] pub fn moveto(&self, h: usize, w: usize, dir: char) -> Option { match dir { 'R' => self._moveto(h, w, DIR4[0]), 'D' => self._moveto(h, w, DIR4[1]), 'L' => self._moveto(h, w, DIR4[2]), 'U' => self._moveto(h, w, DIR4[3]), _ => unreachable!(), } } } }