国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个8×88 \times 88×8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。
而我们的主人公小Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。
小Q找到了一张由N×MN \times MN×M个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。小Q想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。
不过小Q还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。
于是小Q找到了即将参加全国信息学竞赛的你，你能帮助他么？
包含两个整数NNN和MMM，分别表示矩形纸片的长和宽。接下来的NNN行包含一个N ×MN \ \times MN ×M的010101矩阵，表示这张矩形纸片的颜色（000表示白色，111表示黑色）。
包含两行，每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积，第二行为可以找到的最大矩形棋盘的面积（注意正方形和矩形是可以相交或者包含的）。
输入：
3 3
1 0 1
0 1 0
1 0 0
输出：
4
6
对于20%20\%20%的数据，N,M≤80N, M ≤ 80N,M≤80
对于40%40\%40%的数据，N,M≤400N, M ≤ 400N,M≤400
对于100%100\%100%的数据，N,M≤2000N, M ≤ 2000N,M≤2000
嗯。。这题很明显是一个求最大子矩阵的题，我们再观察一下数据范围，嗯。。这数据并不大
那么这个时候就可以用悬线法（超级无敌牛逼的简直为矩阵问题量身定做的神仙算法bling bling），
不懂的读者可以去看看我的另一篇blog洛谷4147（悬线法），在那篇blog中我有详细介绍过悬线法，
而这篇blog与那篇极为相像，此处就不多赘述悬线法了，废话不多说（虽然已经说了很多）贴代码：
code:
#include<bits/stdc++.h> #define fo(i,j,k) for(register int i=j;i<=k;i++) #define fd(i,j,k) for(register int i=j;i>=k;i--) #define ll long long #define m(a) memset(a,0,sizeof(a)) using namespace std; int n,m,x; int l[2001][2001],r[2001][2001],up[2001][2001]; int mp[2001][2001]; int ans1,ans2; int main() { cin>>n>>m; fo(i,1,n) fo(j,1,m) { scanf("%d",&x); mp[i][j]=x; l[i][j]=j; r[i][j]=j; up[i][j]=1; } fo(i,1,n) fo(j,2,m) { if(mp[i][j]!=mp[i][j-1]) l[i][j]=l[i][j-1]; } fo(i,1,n) fd(j,m-1,1) { if(mp[i][j]!=mp[i][j+1]) r[i][j]=r[i][j+1]; } fo(i,1,n) fo(j,1,m) { if(i>1 && mp[i][j]!=mp[i-1][j]) { l[i][j]=max(l[i-1][j],l[i][j]); r[i][j]=min(r[i-1][j],r[i][j]); up[i][j]=up[i-1][j]+1; } ans1=max(ans1,(r[i][j]-l[i][j]+1)*up[i][j]); int cd; cd=min(r[i][j]-l[i][j]+1,up[i][j]); ans2=max(ans2,cd*cd); } cout<<ans2<<endl<<ans1; return 0; }
嗯。。。整体难度其实不难，就是最后输出时注意顺序（害死我了qwq）
有兴趣的可以做一下：
悬线法题目:P1169 棋盘制作 p4147 玉蟾宫 p2701 巨大的牛棚 p1387 最大正方形
原文：https://www.cnblogs.com/tomo-ROK/p/12246758.html