P1387 最大正方形

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

输入格式 输入文件第一行为两个整数n,m（1<=n,m<=100），接下来n行，每行m个数字，用空格隔开，0或1.

输出格式 一个整数，最大正方形的边长

分析 这是一道前缀和的题目，解题思路是，可以枚举正方形的边长，看是否有这样的正方形存在， 存在就替换，直到找到最大的一个

#include<bits/stdc++.h> using namespace std; typedef long long LL; int n, m; int a[101][101], b[101][101]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { cin >> a[i][j]; b[i][j] = b[i-1][j] + b[i][j-1]-b[i-1][j-1]+ a[i][j]; } int ans = 1; int l = 2; while (l <= n || l <= m) { for (int i = l; i <= n; i++) { for (int j = l; j <= m; j++) { if (b[i][j] - b[i-l][j] - b[i][j-l] + b[i-l][j-l] == l*l) ans = max(ans, l); } } l++; } cout << ans; return 0; }

In a relationship 今天学到的一个词。