#include #include #define rep(i,n) for(int i=0;i vi; typedef vector vl; typedef vector> vvi; typedef vector> vvl; typedef long double ld; typedef pair P; template ostream& operator<<(ostream& os, const static_modint& a) {os << a.val(); return os;} template ostream& operator<<(ostream& os, const dynamic_modint& a) {os << a.val(); return os;} template istream& operator>>(istream& is, static_modint& a) {long long x; is >> x; a = x; return is;} template istream& operator>>(istream& is, dynamic_modint& a) {long long x; is >> x; a = x; return is;} template istream& operator>>(istream& is, vector& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;} template ostream& operator<<(ostream& os, const pair& p){os << p.first << ' ' << p.second; return os;} template ostream& operator<<(ostream& os, const vector& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;} template ostream& operator<<(ostream& os, const vector>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;} template ostream& operator<<(ostream& os, const set& se){for(T x : se) os << x << " "; os << "\n"; return os;} template ostream& operator<<(ostream& os, const unordered_set& se){for(T x : se) os << x << " "; os << "\n"; return os;} template ostream& operator<<(ostream& os, const atcoder::segtree& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;} template ostream& operator<<(ostream& os, const atcoder::lazy_segtree& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;} template void chmin(T& a, T b){a = min(a, b);} template void chmax(T& a, T b){a = max(a, b);} const int INF = 1001001001; using S = pair; S _INF(INF, INF); S _ZERO(0, 0); using F = pair; S apply(F f, S x){ return S(x.first + f.first, x.second + f.second); } template struct Dijkstra{ struct Edge{ int from, to; F cost; Edge(int from, int to, F cost) : from(from), to(to), cost(cost) {}; }; int n, m; vector initialized; vector E; vector> G; map> dist; map> idx; Dijkstra(int _n) : n(_n), m(0), initialized(n, false), G(n){} void add_edge(int from, int to, F cost){ Edge e(from, to, cost); E.push_back(e); G[from].emplace_back(m); m++; } void calc(int s){ initialized[s] = true; dist[s] = vector(n, _INF); idx[s] = vector(n, -1); priority_queue, vector>, greater>> pq; pq.emplace(_ZERO, s, -1); while(pq.size()){ auto [dist_from, from, index] = pq.top(); pq.pop(); if(dist[s][from] <= dist_from) continue; dist[s][from] = dist_from; idx[s][from] = index; for(int index : G[from]){ int to = E[index].to; S dist_to = apply(E[index].cost, dist_from); if(dist[s][to] <= dist_to) continue; pq.emplace(dist_to, to, index); } } } int farthest(int s){ if(!initialized[s]) calc(s); int idx = 0; rep(i, n) if(dist[s][i] > dist[s][idx]) idx = i; return idx; } S get_dist(int s, int t){ if(!initialized[s]) calc(s); return dist[s][t]; } vector restore(int s, int t){ if(!initialized[s]) calc(s); if(dist[s][t] == _INF) return vector(0); vector res; while(idx[s][t] != -1){ auto e = E[idx[s][t]]; res.push_back(idx[s][t]); t = e.from; } reverse(res.begin(), res.end()); return res; } }; int main(){ int h, w; cin >> h >> w; vector s(h); cin >> s; Dijkstra graph(h * w); rep(y, h) rep(x, w - 1){ if(s[y][x] == '.' and s[y][x + 1] == '.'){ graph.add_edge(y * w + x, y * w + (x + 1), F(1, 0)); graph.add_edge(y * w + (x + 1), y * w + x, F(1, 0)); } } rep(x, w) rep(y, h - 1){ if(s[y][x] == '.' and s[y + 1][x] == '.'){ graph.add_edge(y * w + x, (y + 1) * w + x, F(0, 1)); graph.add_edge((y + 1) * w + x, y * w + x, F(0, 1)); } } auto ans = graph.get_dist(0, h * w - 1); if(ans == _INF){ cout << "No\n"; }else{ cout << "Yes\n"; cout << ans; } return 0; }