zkx06111's Blog

//O(n^2)动态规划,f[i][j]前后分别表示以(i,j)为右下角的最多条数
//预处理出数组r[i][j]前后分别表示(i,j)左边和右边鱼的条数
//rn[i][j]表示(i,j)上方鱼的条数
//为了省空间只好回收利用数组了。。。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int ans=0,n,m,f[2505][2505];
unsigned short r[2505][2505],rn[2505][2505],pond[2505][2505];
int main(){
	scanf("%d%d",&n,&m);
	
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j){
			scanf("%d",&pond[i][j]);
			r[i][j]=r[i][j-1]+pond[i][j];
			//printf("r%d,%d=%d\n",i,j,r[i][j]);
		}
	for (int j=1;j<=n;++j)
		for (int i=1;i<=m;++i){
			rn[j][i]=rn[j-1][i]+pond[j][i];
			//printf("rm%d,%d=%d\n",j,i,rn[j][i]);
		}
	
	for (int i=1;i<=m;++i) f[1][i]=pond[1][i];
	for (int j=1;j<=n;++j) f[j][1]=pond[j][1];
	
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j){
			if (i==1 || j==1){
				ans=max(ans,f[i][j]);
				continue;
			}
			if (pond[i][j]==0){
				f[i][j]=0;
				continue;
			}
			f[i][j]=1;
			if (r[i][j-1]==r[i][j-f[i-1][j-1]-1]
				&& rn[i-1][j]==rn[i-f[i-1][j-1]-1][j])
				f[i][j]=f[i-1][j-1]+1;
			//printf("f%d,%d=%d\n",i,j,f[i][j]);
			ans=max(ans,f[i][j]);
		}
	
	memset(f,0,sizeof(f));
	
	for (int i=1;i<=m;++i) f[1][i]=pond[1][i];
	for (int j=1;j<=n;++j) f[j][m]=pond[j][m];
	
	for (int i=1;i<=n;++i)
		for (int j=m;j>0;--j){
			r[i][j]=r[i][j+1]+pond[i][j];
			//printf("r%d,%d=%d\n",i,j,r[i][j]);
		}
	
	for (int i=1;i<=n;++i)
		for (int j=m;j>0;--j){
			if (i==1 || j==m){
				ans=max(ans,f[i][j]);
				continue;
			}
			if (pond[i][j]==0){
				f[i][j]=0;
				continue;
			}
			f[i][j]=1;
			if (i==2 && j==3) {
				//printf("  %d,%d=%d\n",i-1,j,rn[i-1][j]);
				//printf("  %d,%d=%d\n",i-g[i-1][j+1]-1,j,rn[i-g[i-1][j+1]-1][j]);
			}
			if (r[i][j+f[i-1][j+1]+1]==r[i][j+1]
				&& rn[i-1][j]==rn[i-f[i-1][j+1]-1][j]){
				//printf("!!%d,%d!!\n%d,",i,j,f[i-1][j+1]);
				f[i][j]=f[i-1][j+1]+1;
			}	
			//printf("g%d,%d=%d\n",i,j,f[i][j]);
			ans=max(ans,f[i][j]);
		}
	
	printf("%d",ans);
	
	return 0;
}