/*#include #include using namespace std; int n,m; char d[101][101]; void read() { int i,j; scanf("%d%d",&n,&m); for(i = 0; i < n; i++){ getchar(); for(j = 0; j < m; j++){ char c = getchar(); d[i][j] = c; } } } int solve(){ int best = -1,max = 0,last = -1,li = 0; int i = 0,j = 0; while(i < n){ if(max > best) best = max; if(d[i][j] != '&') max ++,j ++; if(i != li){ int cj = j - 1; while(cj >= 0 && d[i][cj] != '&') cj--; if(cj > last) last = cj; } if(j == m || d[i][j] == '&') { if(max > best) best = max; i++; -- j; // max ++; while(d[i][j] == '&' && j > last){ --j,--max; if(i > 0 && d[i - 1][j] == '&') return best; } if(j <= last) return best; } if(j < 0) return best; li = i; } return best; } int main() { freopen("f.in","r",stdin); read(); printf("%d\n",solve()); return 0; }*/ #include #include #include #include #define mkp make_pair #define ff first #define ss second #define punct pair using namespace std; int D[110][110],n,m; punct start, end1; void construct(); void bfs(){ int i = 1, j = 1; construct(); queue Q; punct now, now2; Q.push(start); while (Q.empty() == false){ now = Q.front(); Q.pop(); i = now.ff; j = now.ss; if(i <= n && j <= m){ if(i < n && D[i + 1][j] != -1) { D[i + 1][j] = max(D[i][j],D[i + 1][j - 1]) + 1; Q.push(mkp(i+1, j)); } if(j < m && D[i][j + 1] != -1) { D[i][j + 1] = max(D[i][j],D[i - 1][j + 1]) + 1; Q.push(mkp(i, j+1)); } } } } void construct() { int p,x,y,i,j; scanf("%d%d",&n,&m); for(i = 1; i <= n; i++){ getchar(); for(j = 1; j <= m; j++){ char c = getchar(); if(c == '.') D[i][j] = 1; else D[i][j] = -1; } } start.ff = 1; start.ss = 1; } int main() { // freopen("f.in","r",stdin); bfs(); int max = 0; if(D[1][1] != -1){ for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){ if(D[i][j] > max) max = D[i][j]; } printf("%d\n",max); } else printf("%d\n",0); return 0; }