#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; int n, m; string a[1010]; int b[1010][1010]; int c; int dx[8]={1, -1, 0, 0, 1, 1, -1, -1}, dy[8]={0, 0, 1, -1, 1, -1, 1, -1}; void dfs(int x, int y, int v){ b[x][y]=v; for(int k=0; k<4; k++){ int x1=x+dx[k], y1=y+dy[k]; if(x1<0 || x1>=n || y1<0 || y1>=m) continue; if(a[x1][y1]=='x' || b[x1][y1]>=0) continue; dfs(x1, y1, v); } } void dfs2(int x, int y, int v, int &cnt){ cnt++; b[x][y]=v; for(int k=0; k<8; k++){ int x1=x+dx[k], y1=y+dy[k]; if(x1<0 || x1>=n || y1<0 || y1>=m) continue; if(b[x1][y1]>=0) continue; if(a[x1][y1]=='.'){ if(k<4) dfs(x1, y1, v); }else dfs2(x1, y1, v, cnt); } } int cnt[1000010]; vector> g; int dp[2][1000010]; void dfs3(int x, int p){ for(auto y:g[x]){ if(y==p) continue; dfs3(y, x); dp[1][x]+=dp[0][y]; dp[0][x]+=max(dp[0][y], dp[1][y]); } dp[1][x]+=cnt[x]; } int main() { cin>>n>>m; for(int i=0; i>s; for(int j=1; j<=m; j++) a[i][j]=s[j-1]; } n+=2, m+=2; dfs(0, 0, 0); c++; for(int i=0; i