题目描述
国际象棋是世界上最古老的博弈游戏之一, 和中国的围棋, 象棋以及日本的将棋同享盛名. 据说国际象棋起源于易经的思想, 棋盘是一个 8 \times 88*8 大小的黑白相间的方阵, 对应八八六十四卦, 黑白对应阴阳.
而我们的主人公小 Q, 正是国际象棋的狂热爱好者. 作为一个顶尖高手, 他已不满足于普通的棋盘与规则, 于是他跟他的好朋友小 W 决定将棋盘扩大以适应他们的新规则.
小 Q 找到了一张由 N \times MN*M 个正方形的格子组成的矩形纸片, 每个格子被涂有黑白两种颜色之一. 小 Q 想在这种纸中裁减一部分作为新棋盘, 当然, 他希望这个棋盘尽可能的大.
不过小 Q 还没有决定是找一个正方形的棋盘还是一个矩形的棋盘 (当然, 不管哪种, 棋盘必须都黑白相间, 即相邻的格子不同色), 所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积, 从而决定哪个更好一些.
于是小 Q 找到了即将参加全国信息学竞赛的你, 你能帮助他么?
输入输出格式
输入格式:
包含两个整数 NN 和 MM, 分别表示矩形纸片的长和宽. 接下来的 NN 行包含一个 N \ \times MN*M 的 0101 矩阵, 表示这张矩形纸片的颜色 (00 表示白色, 11 表示黑色).
输出格式:
包含两行, 每行包含一个整数. 第一行为可以找到的最大正方形棋盘的面积, 第二行为可以找到的最大矩形棋盘的面积 (注意正方形和矩形是可以相交或者包含的).
输入输出样例
输入样例 #1
- 3 3
- 1 0 1
- 0 1 0
- 1 0 0
输出样例 #1 4 6
说明
对于 20\%20% 的数据, N, M ≤ 80N,M≤80
对于 40\%40% 的数据, N, M ≤ 400N,M≤400
对于 100\%100% 的数据, N, M ≤ 2000N,M≤2000
做法就不说了, 就是悬线法的模板加了一点改动~~~
- #include<bits/stdc++.h>
- #define ll long long
- #define ull unsigned long long
- #define inf 0x3f3f3f3f
- #define mp make_pair
- #define met(a,x) memset(a,x,sizeof(a))
- using namespace std;
- const int mod=1e9+7;
- const int N=2010,M=2010;
- int l[N][M],r[N][M],h[N][M],c[N][M];
- int n,m;
- void init()
- {
- for (int i=1; i<=n; i++)
- {
- l[i][0]=0;// 左
- r[i][m+1]=0;// 右
- }
- for (int i=1; i<=m; i++)
- h[0][i]=0;// 上
- }
- int main()
- {
- iOS::sync_with_stdio(false);
- cin.tie(0);
- int ans=0,x,y,tmp;
- cin>>n>>m;
- for (int i=1; i<=n; i++)
- for (int j=1; j<=m; j++)
- cin>>c[i][j];
- init();
- for (int i=1; i<=n; i++)
- {
- for (int j=1; j<=m; j++)
- {
- if (c[i][j]==c[i][j-1])
- l[i][j]=1;
- else
- l[i][j]=l[i][j-1]+1;
- if (c[i][j]==c[i-1][j])
- h[i][j]=1;
- else
- h[i][j]=h[i-1][j]+1;
- if (c[i][m-j+1]==c[i][m-j+2])
- r[i][m-j+1]=1;
- else
- r[i][m-j+1]=r[i][m-j+2]+1;
- }
- }
- int ans2=0,cnt;
- for (int i=1; i<=n; i++)
- {
- for (int j=1; j<=m; j++)
- {
- if (h[i][j]>1)
- {
- l[i][j]=min(l[i][j],l[i-1][j]);
- r[i][j]=min(r[i][j],r[i-1][j]);
- }
- ans=max(ans,h[i][j]*(l[i][j]+r[i][j]-1));
- cnt=min(h[i][j],l[i][j]+r[i][j]-1);
- ans2=max(ans2,cnt*cnt);
- }
- }
- cout<<ans2<<endl<<ans<<endl;
- return 0;
- }// 复杂度 O(n^2)
- winner_yh
来源: http://www.bubuko.com/infodetail-2776310.html