首先把矩阵转化一下，把横纵坐标和为偶数点的值取反，这样就转化成求最大的'0'或'1'矩阵。
这道题每个数字是在格子内的，不能在边界包含障碍点。
求最大的0矩阵时，把1作为障碍点。求1同理。
然后求最接近的就可以用树状数组求解啦~
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const int N=2100,Inf=(int)1e9; 9 int n,m,a1,a2;10 int a[N][N],l[N][N],r[N][N],last[N][N],cl[N][N],cr[N][N];11 12 13 int minn(int x,int y){ return x y ? x:y;}15 16 void add(int x,int y,int d)17 {18 for(int i=y;i<=m;i+=(i&(-i))) cl[x][i]=maxx(cl[x][i],d);19 for(int i=y;i>=1;i-=(i&(-i))) cr[x][i]=minn(cr[x][i],d);20 }21 22 int get(int x,int y,int tmp)23 {24 if(tmp==0)25 {26 int ans=0;27 for(int i=y-1;i>=1;i-=(i&(-i))) ans=maxx(ans,cl[x][i]);28 if(ans==0) return 1;29 else return ans+1;30 }31 else32 {33 int ans=Inf;34 for(int i=y+1;i<=m;i+=(i&(-i))) ans=minn(ans,cr[x][i]);35 if(ans>=Inf) return m;36 else return ans-1;37 }38 }39 40 void solve(int tmp)41 {42 memset(cl,0,sizeof(cl));43 memset(cr,63,sizeof(cr));44 for(int i=1;i<=n;i++)45 for(int j=1;j<=m;j++)46 {47 if(a[i][j]==tmp) add(i,j,j);48 }49 memset(l[0],0,sizeof(l[0]));50 memset(r[0],63,sizeof(r[0]));51 for(int i=1;i<=n;i++)52 {53 for(int j=1;j<=m;j++)54 {55 if(a[i][j]==tmp) continue;56 if(a[i-1][j]==tmp)57 {58 l[i][j]=get(i,j,0);//debug59 r[i][j]=get(i,j,1);//debug60 last[i][j]=i-1;61 }62 else63 {64 l[i][j]=maxx(l[i-1][j],get(i,j,0));65 r[i][j]=minn(r[i-1][j],get(i,j,1));66 last[i][j]=last[i-1][j];67 }68 int xx=r[i][j]-l[i][j]+1;69 int yy=i-last[i][j];70 a1=maxx(a1,minn(xx,yy)*minn(xx,yy));71 a2=maxx(a2,xx*yy);72 }73 }74 }75 76 int main()77 {78 freopen("a.in","r",stdin);79 scanf("%d%d",&n,&m);80 a1=0;a2=0;81 for(int i=1;i<=n;i++)82 for(int j=1;j<=m;j++)83 {84 scanf("%d",&a[i][j]);85 if((i+j)%2==0) a[i][j]^=1;86 }87 solve(1);88 solve(0);89 printf("%d\n%d\n",a1,a2);90 return 0;91 }