洛谷 P1387 最大正方形 C语言

题目描述

在一个 n × m 的只包含 0 和 1 的矩阵里找出一个不包含 0 的最大正方形，输出边长。

输入格式

输入文件第一行为两个整数 n, m (1 ≤ n, m ≤ 100)，接下来 n 行，每行 m 个数字，用空格隔开，0 或 1。

输出格式

一个整数，最大正方形的边长。

输入输出样例

输入 #1
 

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

输出 #1
 

2

思路：

代码如下：
 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;
const int N = 1010;
int n, m;
int arr[N][N];
ll pre[N][N]; // 使用 long long 类型以避免大数溢出int main() 
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> arr[i][j];pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + arr[i][j];}}int ans = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {for (int l = 1; l <= min(n - i + 1, m - j + 1); l++)// 确保不越界{ if (pre[i+l-1][j+l-1] - pre[i-1][j+l-1] - pre[i+l-1][j-1] + pre[i-1][j-1] == l * l){ans = max(ans, l);}else{break; // 如果当前边长不满足，则无需继续检查更大的边长}}}}cout << ans << endl;return 0;
}