题目大意
给定一个二维数组,要求找到满足限制条件的最大正方形,
限制条件为:正方形内所有元素都不小于该正方形的边长。
解题思路
显然可以二分答案,解题的关键如何快速判断正方形是否满足该限制条件。
对于当前正方形边长x,我们可以预处理二维数组,将不小于x的元素置一,反之,置零。
计算出新数组的二位前缀和,若某个正方形所有元素的和等于\(x^2\),则该正方形满足题意。
参考代码
#include <bits/stdc++.h>
using namespace std;
void work()
{
int n, m;
cin >> n >> m;
vector<vector<int>> a(n + 1, vector<int> (m + 1));
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
cin >> a[i][j];
}
}
auto check = [&](int x)
{
vector<vector<int>> s(n + 1, vector<int> (m + 1));
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
s[i][j] = a[i][j] >= x ? 1 : 0;
}
}
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];
}
}
for (int i = 1; i <= n - x + 1; ++i)
{
for (int j = 1; j <= m - x + 1; ++j)
{
if (s[i + x - 1][j + x - 1] - s[i - 1][j + x - 1] - s[i + x - 1][j - 1] + s[i - 1][j - 1] == x * x)
{
return true;
}
}
}
return false;
};
int l = 1, r = n, ans = 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(mid))
{
ans = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin >> T;
while (T--)
{
work();
}
return 0;
}
标签:Map,int,正方形,vector,Valiant,New
From: https://www.cnblogs.com/hetailang/p/17011993.html