题目描述
国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个8*8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。
而我们的主人公小Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。
小Q找到了一张由N*M个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。小Q想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。
不过小Q还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。
于是小Q找到了即将参加全国信息学竞赛的你，你能帮助他么？
输入输出格式
输入格式：
包含两个整数N和M，分别表示矩形纸片的长和宽。接下来的N行包含一个N * M的01矩阵，表示这张矩形纸片的颜色（0表示白色，1表示黑色）。
输出格式：
包含两行，每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积，第二行为可以找到的最大矩形棋盘的面积（注意正方形和矩形是可以相交或者包含的）。
输入输出样例
输入样例#1：
3 31 0 10 1 01 0 0
输出样例#1：
46
说明
对于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#include #include #include #define LL long long intusing 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\n%d\n",ans1,ans2);}int main(){ init(); solve(); return 0;}