P1387 最大正方形

题目描述

在一个 n\times mn×m 的只包含 00 和 11 的矩阵里找出一个不包含 00 的最大正方形，输出边长。

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

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

输出 #1复制

2

#include<stdio.h>
#define	max(a,b) a>b? a:b	
int a[103][103];
int sum[103][103];
int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		//使用二位前缀和，for循环中i，j的初始值应设置为1 
		for (int j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
			sum[i][j] = a[i][j] + sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
			//二位前缀和的计算 
		}
	}
	int ans = 0;
	int l = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (sum[i][j] - sum[i - l][j] - sum[i][j - l] + sum[i - l][j - l] == l * l) {
				//边长为l的正方形对应的所有数值加和 
				ans = max(ans, l);
				l++;
			}
		}
	}
	printf("%d", ans);
}