#include #include #include #include #include #include using namespace std; using ll = long long; #define rep(i, n) for (int i = 0; i < n; ++i) int main() { ll h, w; cin >> h >> w; vector s(h); rep(i, h) cin >> s[i]; s[0][0] = '.'; s[h-1][w-1] = '.'; auto itop = [&](ll i) { return pair{i / w, i % w}; }; auto ptoi = [&](pair p) { return p.first * w + p.second; }; vector> g1(h * w), g2(h * w); rep(i, h) { rep(j, w) { if(s[i][j] == '.') { if(i < h-1 && s[i+1][j] == '.') g1[ptoi({i, j})].emplace_back(ptoi({i+1, j})); if(j < w-1 && s[i][j+1] == '.') g1[ptoi({i, j})].emplace_back(ptoi({i, j+1})); } } } rep(i, h) { rep(j, w) { if(s[i][j] == '.') { if(i > 0 && s[i-1][j] == '.') g2[ptoi({i, j})].emplace_back(ptoi({i-1, j})); if(j > 0 && s[i][j-1] == '.') g2[ptoi({i, j})].emplace_back(ptoi({i, j-1})); } } } vector dist1(h*w, false), dist2(h * w, false); dist1[0] = true; dist2.back() = true; queue q1, q2; q1.push(0); q2.push(h * w - 1); while(!q1.empty()) { auto v = q1.front(); q1.pop(); for(auto c : g1[v]) { if(dist1[c]) continue; dist1[c] = true; q1.emplace(c); } } while(!q2.empty()) { auto v = q2.front(); q2.pop(); for(auto c : g2[v]) { if(dist2[c]) continue; dist2[c] = true; q2.emplace(c); } } if(dist1.back()) { cout << h + w - 2 << endl; return 0; } rep(i, h-1) { ll j = 0; while(j < w && !dist1[i * w + j]) j++; for(; j