#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=0;i--){ if(s[h-1][i] == '#'){ l=i; break; } } if(r>l){ cout << h+w-1 << "\n"; return; } int d=h,u=-1; rep(i,0,h){ if(s[i][0] == '#'){ d=i; break; } } for(int i=h-1;i>=0;i--){ if(s[i][w-1] == '#'){ u=i; break; } } if(d>u){ 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(); }