P1387 最大正方形

题目链接:https://www.luogu.com.cn/problem/P1387

• 二维前缀和模版题

#include<bits/stdc++.h>
using namespace std;
int n, m, a[105][105], s[105][105];
int ans;
int main()
{
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			cin>>a[i][j];//输入矩阵 
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)	
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];//二维前缀和 
	for(int x1=1; x1<=n; x1++)
		for(int y1=1; y1<=m; y1++)
			for(int len=0; len+x1<=n && len+y1<=m; len++){//边长增量，len从0开始考虑1个点就是个正方形 
				int x2=x1+len;//右下点坐标位置 
				int y2=y1+len;
				int mj=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];//二维区间和 
				if(mj==(len+1)*(len+1))//判断是否为正方形 
					ans=max(ans, len+1);
			}
	cout<<ans;

	return 0;
}