# 洛谷 P1387 最大正方形（前缀和，二分）()-其他

## 洛谷 P1387 最大正方形（前缀和，二分）()

### 参考代码

• 暴力
``````#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N], s[N][N], n, m;
int check(int mid)
{
for (int i = mid; i <= n; i ++ )
{
for (int j = mid; j <= m; j ++ )
{
if (s[i][j] - s[i - mid][j] - s[i][j - mid] + s[i - mid][j - mid] == mid * mid) return 1;
}
}
return 0;
}

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 >> a[i][j];
s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
int l = 1, r = min(n, m);
for (int i = r; i >= 1; i -- )
{
if (check(i))
{
cout << i << endl;
break;
}
}
return 0;
}
``````
• 二分答案
``````#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N], s[N][N], n, m;
int check(int mid)
{
for (int i = mid; i <= n; i ++ )
{
for (int j = mid; j <= m; j ++ )
{
if (s[i][j] - s[i - mid][j] - s[i][j - mid] + s[i - mid][j - mid] >= mid * mid) return 1;
}
}
return 0;
}
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 >> a[i][j];
s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
int l = 1, r = min(n, m);
while (l < r)
{
int mid = l + (r - l + 1) / 2;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l << '\n';
return 0;
}
``````
————————

### 参考代码

• 暴力
``````#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N], s[N][N], n, m;
int check(int mid)
{
for (int i = mid; i <= n; i ++ )
{
for (int j = mid; j <= m; j ++ )
{
if (s[i][j] - s[i - mid][j] - s[i][j - mid] + s[i - mid][j - mid] == mid * mid) return 1;
}
}
return 0;
}

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 >> a[i][j];
s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
int l = 1, r = min(n, m);
for (int i = r; i >= 1; i -- )
{
if (check(i))
{
cout << i << endl;
break;
}
}
return 0;
}
``````
• 二分答案
``````#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N], s[N][N], n, m;
int check(int mid)
{
for (int i = mid; i <= n; i ++ )
{
for (int j = mid; j <= m; j ++ )
{
if (s[i][j] - s[i - mid][j] - s[i][j - mid] + s[i - mid][j - mid] >= mid * mid) return 1;
}
}
return 0;
}
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 >> a[i][j];
s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
int l = 1, r = min(n, m);
while (l < r)
{
int mid = l + (r - l + 1) / 2;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l << '\n';
return 0;
}
``````