题目描述
国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个8*8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。
而我们的主人公小Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。
小Q找到了一张由N*M个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。小Q想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。
不过小Q还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。
于是小Q找到了即将参加全国信息学竞赛的你，你能帮助他么？
输入输出格式
输入格式：
包含两个整数N和M，分别表示矩形纸片的长和宽。接下来的N行包含一个N * M的01矩阵，表示这张矩形纸片的颜色（0表示白色，1表示黑色）。
输出格式：
包含两行，每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积，第二行为可以找到的最大矩形棋盘的面积（注意正方形和矩形是可以相交或者包含的）。
输入输出样例
输入样例#1：
3 3 1 0 1 0 1 0 1 0 0
输出样例#1：
4 6
说明
对于20%的数据，N, M ≤ 80
对于40%的数据，N, M ≤ 400
对于100%的数据，N, M ≤ 2000
题解
首先，我们选出所有01联通块，只需要一个很简单的做法，就是隔一个反转一个数字，具体来讲，就是将i+j为偶数的(i,j)反转
反转之后呢，就是 最大同色矩形问题
最大同色矩形问题
最大同色矩形问题，顾名思义，就是求一个矩阵中的最大同色矩形
用到 动归 + 并查集 + 排序
具体而言，我们先求出h[i][j]为从(i,j)点向右扩展最远的距离
利用dp可以在O(n^2)内求出
for (int i = 1; i <= N; i++){
h[i][M] = 1;
for (int j = M - 1; j >= 1; j--){
h[i][j] = (A[i][j] == A[i][j + 1] ? h[i][j + 1] + 1 : 1);
}
}
由于是纵向边，我们就在每一列讨论：
对于j这一列，我们按h的大小从大到小枚举，枚举到当前行i时，包含i的矩形的横向边长度一定是i，而纵向边的长度就是当前从i出发向上向下能经过已访问点的最长长度【因为只有已访问的点的h比i大，才能使h[i][j]作为横向长度】，具体用两个并查集l[i],r[i]实现
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
using namespace std;
const int maxn = 2005,maxm = 100005,INF = 2000000000;
inline int read(){
int out = 0,flag = 1;char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1;c = getchar();}
while (c >= 48 &&c <= 57) {out = out * 10 + c - 48;c = getchar();}
return out * flag;
}
int N,M,A[maxn][maxn],l[maxn],r[maxn],h[maxn][maxn];
bool vis[maxn];
struct node{
int len,id;
}tmp[maxn];
inline bool operator < (const node& a,const node& b){
return a.len > b.len;
}
inline int findl(int u) {return u == l[u] ? u : l[u] = findl(l[u]);}
inline int findr(int u) {return u == r[u] ? u : r[u] = findr(r[u]);}
void init(){
N = read();
M = read();
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
A[i][j] = read()^((i^j) & 1);
}
void solve(){
int ans1 = 0,ans2 = 0,a,b;
for (int i = 1; i <= N; i++){
h[i][M] = 1;
for (int j = M - 1; j >= 1; j--){
h[i][j] = (A[i][j] == A[i][j + 1] ? h[i][j + 1] + 1 : 1);
}
}
for (int j = 1; j <= M; j++){
for (int i = 1; i <= N; i++){
tmp[i].len = h[i][j];
tmp[i].id = i;
vis[i] = false;
l[i] = r[i] = i;
}
sort(tmp + 1,tmp + 1 + N);
for (int i = 1; i <= N; i++){
int k = tmp[i].id;
vis[k] = true;
if (k > 1 && vis[k - 1] && A[k - 1][j] == A[k][j]){
l[k] = k - 1; r[k - 1] = k;
}
if (k < N && vis[k + 1] && A[k + 1][j] == A[k][j]){
r[k] = k + 1; l[k + 1] = k;
}
a = findr(k) - findl(k) + 1;
b = tmp[i].len;
ans1 = max(ans1,min(a,b) * min(a,b));
ans2 = max(ans2,a * b);
}
}
printf("%d
%d
",ans1,ans2);
}
int main(){
init();
solve();
return 0;
}