用dp[x][y]表示以(x,y)点为右下角，所形成的图形的最大边长
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int n; char s[502][502]; int dp1[502][502],dp2[502][502]; int DP1(int x,int y){ if(s[x][y]=='.') return 0; if(x==0||y==0) return s[x][y]=='x' ? 1:0; if(dp1[x][y]!=-1) return dp1[x][y]; int ret=1000; ret=min(ret,DP1(x-1,y)); ret=min(ret,DP1(x,y-1)); if(s[x-ret][y-ret]=='x') return dp1[x][y]=ret+1; else return dp1[x][y]=ret; } int DP2(int x,int y){ if(s[x][y]=='.') return 0; if(x==0||y==0||y==n-1||s[x-1][y]=='.') return s[x][y]=='x' ? 1:0; if(dp2[x][y]!=-1) return dp2[x][y]; int ret=1000; ret=min(ret,DP2(x-1,y-1)); ret=min(ret,DP2(x-1,y+1)); if(x-2*ret>=0){ if(s[x-2*ret][y]=='x'&&s[x-2*ret+1][y]=='x') return dp2[x][y]=ret+1; } return dp2[x][y]=max(ret,1); } int main(){ while(~scanf("%d",&n)){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>s[i][j]; } } memset(dp1,-1,sizeof dp1); memset(dp2,-1,sizeof dp2); int ans=0; for(int i=n-1;i>=0;i--){ for(int j=n-1;j>=0;j--){ if(s[i][j]=='x'){ ans+=DP1(i,j)-1+DP2(i,j)-1; } } } printf("%d ",ans); } return 0; }