P1387 最大正方形 题解

注意细节

通过二维前缀和判定矩形内是否全为1，计算和等于长度的平方就判断为是

复杂度\(\Theta (n^2\log{n})\)

#include <bits/stdc++.h>

#define N (int)(105)

using namespace std;

int mp[N][N];
int s[N][N];
int n,m;

bool check(int lenth)
{
	for(int i = 1;i + lenth - 1 <= n;i++)
	{
		for(int j = 1;j + lenth - 1 <= m;j++)
		{
			if(s[i + lenth - 1][j + lenth - 1] - s[i-1][j + lenth - 1] - s[i + lenth - 1][j-1] + s[i-1][j-1] == lenth * lenth)//
			{
				return true;
			}
		}
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		for(int j =1;j <= m;j++)
		{
			cin >> mp[i][j];
			s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + mp[i][j];
		}
	}
	
	int l = 1, r = min(n,m);
	while(l < r)
	{
		int mid = (l + r) / 2 + 1;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l;
	return 0;
}