use std::{cmp::Reverse, collections::BinaryHeap}; use proconio::{input, marker::Chars}; const DIFFS: [(usize, usize); 4] = [(!0, 0), (0, !0), (0, 1), (1, 0)]; fn main() { input! { (h, w): (usize, usize), ss: [Chars; h], } let mut cost_matrix: Vec>> = vec![vec![None; w]; h]; let mut heap = BinaryHeap::from([Reverse(Node { horizontal_cost: 0, vertical_cost: 0, coord: (0, 0), })]); while let Some(Reverse(node)) = heap.pop() { let (row, col) = node.coord; if cost_matrix[row][col].is_some() { continue; } cost_matrix[row][col] = Some((node.horizontal_cost, node.vertical_cost)); for (diff_row, diff_col) in DIFFS { let adj_row = row.wrapping_add(diff_row); let adj_col = col.wrapping_add(diff_col); let adj_coord = (adj_row, adj_col); if adj_row < h && adj_col < w && ss[adj_row][adj_col] == '.' { let next_node = Node { horizontal_cost: node.horizontal_cost + (diff_col != 0) as usize, vertical_cost: node.vertical_cost + (diff_row != 0) as usize, coord: adj_coord, }; heap.push(Reverse(next_node)); } } } match cost_matrix[h - 1][w - 1] { Some((horizontal_cost, vertical_cost)) => { println!("Yes\n{} {}", horizontal_cost, vertical_cost) } None => println!("No"), } } struct Node { horizontal_cost: usize, vertical_cost: usize, coord: (usize, usize), } impl PartialEq for Node { fn eq(&self, other: &Self) -> bool { self.horizontal_cost == other.horizontal_cost && self.vertical_cost == other.vertical_cost } } impl Eq for Node {} impl PartialOrd for Node { fn partial_cmp(&self, other: &Self) -> Option { Some(self.cmp(other)) } } impl Ord for Node { fn cmp(&self, other: &Self) -> std::cmp::Ordering { match self.horizontal_cost.cmp(&other.horizontal_cost) { core::cmp::Ordering::Equal => {} ord => return ord, } self.vertical_cost.cmp(&other.vertical_cost) } }