洛谷-P1169 棋盘制作(悬线法)

国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个 $8\times 8$8×8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。

而我们的主人公 $小Q$小Q ，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友 $小W$小W 决定将棋盘扩大以适应他们的新规则。

$小Q$小Q 找到了一张由 $N\times M$N×M个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。 $小Q$小Q 想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。

不过 $小Q$小Q 还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。

于是 $小Q$小Q 找到了即将参加全国信息学竞赛的你，你能帮助他么？

输出: 一个 $N\times M$N×M的 $01$01矩阵
输出: 最大正方形和最大矩形面积

#include "bits/stdc++.h"
using namespace std;

const int maxn = 2005;

int ves[maxn][maxn], up[maxn][maxn], Left[maxn][maxn], Right[maxn][maxn];
int temp1=1, temp2=1;

int main() {
    ios::sync_with_stdio(false);
    int N, M;
    cin>>N>>M;
    for(int i=1; i<=N; ++i) {
        for(int j=1; j<=M; ++j) {
            cin>>ves[i][j];
            Left[i][j]=Right[i][j]=j; //记得初始化
            up[i][j]=1;
        }
    }
    for(int i=1; i<=N; ++i) {
        for(int j=2; j<=M; ++j) {
            if(ves[i][j]!=ves[i][j-1]) Left[i][j]=Left[i][j-1]; //对left的预处理
        }
        for(int j=M-1; j; --j) {
            if(ves[i][j]!=ves[i][j+1]) Right[i][j]=Right[i][j+1]; //对right的预处理
        }
    }
    for(int i=1; i<=N; ++i) {
        for(int j=1; j<=M; ++j) {
            if(i>1&&ves[i][j]!=ves[i-1][j]) {
                Left[i][j]=max(Left[i][j],Left[i-1][j]);
                Right[i][j]=min(Right[i][j],Right[i-1][j]);
                up[i][j]=up[i-1][j]+1;
            }
            int as=Right[i][j]-Left[i][j]+1;
            int bs=min(as,up[i][j]);
            temp1=max(temp1,bs*bs);
            temp2=max(temp2,as*up[i][j]);
        }
    }
    cout<<temp1<<endl;
    cout<<temp2<<endl;
}