#include #include using namespace std; using namespace atcoder; #define ll long long #define rep(i,a,b) for(int i=(a);i<(b);i++) #define repl(i,a,b) for(ll i=(a);i<(b);i++) #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() template bool chmin(T &a,T b){if(a>b){a=b;return true;} return false;} template bool chmax(T &a,T b){if(a> h >> w; vector s(h); rep(i,0,h) cin >> s[i]; int INF=1e9; vector dist(h,vector(w,INF)); queue> que; que.push({0,0}); dist[0][0]=0; vector dx={1,0,-1,0},dy={0,1,0,-1}; while(!que.empty()){ auto [x,y]=que.front(); que.pop(); rep(i,0,4){ int nx=x+dx[i],ny=y+dy[i]; if(0<=nx && nx(w,false)); vector r1(h,false); vector c1(w,false); seen1[0][0]=true; que.push({0,0}); r1[0]=true; c1[0]=true; while(!que.empty()){ auto [x,y]=que.front(); que.pop(); rep(i,0,2){ int nx=x+dx[i],ny=y+dy[i]; if(nx(w,false)); vector r2(h,false); vector c2(w,false); seen2[h-1][w-1]=true; que.push({h-1,w-1}); r2[h-1]=true; c2[w-1]=true; while(!que.empty()){ auto [x,y]=que.front(); que.pop(); rep(i,2,4){ int nx=x+dx[i],ny=y+dy[i]; if(0<=nx && 0<=ny && s[nx][ny] != '#' && !seen2[nx][ny]){ seen2[nx][ny]=true; r2[nx]=true; c2[ny]=true; que.push({nx,ny}); } } } rep(i,0,h-1){ if(r1[i] && r2[i+1]){ cout << h+w-1 << "\n"; return; } } rep(i,0,w-1){ if(c1[i] && c2[i+1]){ cout << h+w-1 << "\n"; return; } } cout << h+w << "\n"; return; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T=1; // cin >> T; while(T--) solve(); }