NC20471. [ZJOI2007]棋盘制作
描述
输入描述
第一行包含两个整数N和M，分别表示矩形纸片的长和宽。
接下来的N行包含一个N * M的01矩阵，表示这张矩形纸片的颜色（0表示白色，1表示黑色）。
输出描述
包含两行，每行包含一个整数。
第一行为可以找到的最大正方形棋盘的面积，
第二行为可以找到的最大矩形棋盘的面积（注意正方形和矩形是可以相交或者包含的）。
示例1
输入:
3 3 1 0 1 0 1 0 1 0 0
输出:
4 6
C++(g++ 7.5.0) 解法, 执行用时: 456ms, 内存消耗: 51448K, 提交时间: 2023-02-27 22:11:10
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool v[2005][2005];
int l[2005][2005],r[2005][2005],u[2005][2005];
int main()
{
ios::sync_with_stdio(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>v[i][j],l[i][j]=r[i][j]=j,u[i][j]=1;
for(int i=1;i<=n;++i) for(int j=2;j<=m;++j) if(v[i][j]!=v[i][j-1]) l[i][j]=l[i][j-1];
for(int i=1;i<=n;++i) for(int j=m-1;j;--j) if(v[i][j]!=v[i][j+1]) r[i][j]=r[i][j+1];
int ans=1,dis=1;
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
{
if(v[i][j]!=v[i-1][j]&&i!=1)
{
u[i][j]=u[i-1][j]+1;
l[i][j]=max(l[i][j],l[i-1][j]);
r[i][j]=min(r[i][j],r[i-1][j]);
}
dis=max(dis,min(u[i][j],r[i][j]-l[i][j]+1));
ans=max(ans,u[i][j]*(r[i][j]-l[i][j]+1));
}
cout<<dis*dis<<"\n"<<ans;
return 0;
}
pypy3 解法, 执行用时: 1594ms, 内存消耗: 160008K, 提交时间: 2023-05-31 16:04:01
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
l = [list(range(m)) for _ in range(n)]
r = [list(range(m)) for _ in range(n)]
u = [[1]*m for _ in range(n)]
for i in range(n):
for j in range(1, m):
if arr[i][j-1]!=arr[i][j]:
l[i][j] = l[i][j-1]
for i in range(n):
for j in range(m-2, -1, -1):
if arr[i][j+1]!=arr[i][j]:
r[i][j] = r[i][j+1]
res0 = 1
res = 1
for i in range(n):
for j in range(m):
if i != 0 and arr[i][j]!=arr[i-1][j]:
u[i][j] = u[i-1][j] + 1
l[i][j] = max(l[i-1][j], l[i][j])
r[i][j] = min(r[i-1][j], r[i][j])
c = r[i][j]-l[i][j]+1
res0 = max(res0, min(c, u[i][j])**2)
res = max(res, (r[i][j]-l[i][j]+1)*u[i][j])
print(res0)
print(res)
C++11(clang++ 3.9) 解法, 执行用时: 285ms, 内存消耗: 70944K, 提交时间: 2020-09-28 21:40:31
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e3+5;
int n,m,a[N][N],l[N][N],r[N][N],up[N][N],ans,ans2;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
l[i][j]=r[i][j]=j;up[i][j]=1;
}
for(int i=1;i<=n;i++)for(int j=2;j<=m;j++)if(a[i][j]!=a[i][j-1])l[i][j]=l[i][j-1];
for(int i=1;i<=n;i++)for(int j=m-1;j;j--)if(a[i][j]!=a[i][j+1])r[i][j]=r[i][j+1];
for(int i=1;i<=n;i++)for(int j=1,x,y;j<=m;j++){
if(i>1&&a[i][j]!=a[i-1][j])
l[i][j]=max(l[i][j],l[i-1][j]),r[i][j]=min(r[i][j],r[i-1][j]),up[i][j]=up[i-1][j]+1;
x=r[i][j]-l[i][j]+1;y=min(x,up[i][j]);
ans=max(ans,y*y);ans2=max(ans2,x*up[i][j]);
}
printf("%d\n%d\n",ans,ans2);
return 0;
}