开发者LT的博客
0%

洛谷P1387-最大正方形-题解

发表于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟
前缀和&差分

洛谷P1387-最大正方形-题解

题目描述

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

保证矩阵里有至少一个 。

输入格式

输入文件第一行为两个整数 ，接下来 行，每行 个数字，用空格隔开， 或 。

输出格式

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

输入输出样例 #1

输入 #1

1
2
3
4
5
6
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

输出 #1

1
2

分析

本题的难点在于翻译，”在一个 的只包含 和 的矩阵里找到一个不包含0的最大正方形“

–>拆分出关键词：“不包含0”，“最大”

–>”不包含0“，翻译成，求正方形数组的区间和–二维前缀和数组；

”最大“，结合矩阵中至少有1个1的信息，翻译成，正方形边长从2一直到n和m中的较小值，每个边长，都把整个数组中包含的该边长的正方形遍历一遍，如果找得到符合“不包含0”的正方形，这个边长就是符合要求的，记录下来。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
using namespace std;
int min(int x, int y)
{
	if (x <= y)return x;
	else return y;
}
int main()
{
	int n, m;
	cin >> n >> m;
	//原数组
	vector<vector<int>> ori(n+1, vector<int>(m+1,0));
	//前缀和数组
	vector<vector<int>> sum(n+1, vector<int>(m+1,0));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			//输入原数组
			cin >> ori[i][j];
			//求前缀和数组
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + ori[i][j];
		}
	}
	int ans = 1;//记录最大边长，从1开始，因为题目保证至少有1个1
	int a = 2;//边长从2开始变大，如果2都不行，ans就是1
	while (a <= min(n, m))
	{
		//坐标i,j从（1，1）开始，到边界截止，逐个遍历所有可能的正方形，用前缀和数组计算正方形的矩阵和，
		//如果矩阵和与面积相等，则说明没有0全是1，则ans更新为当前的a
		for (int i = 1; i <= n - a + 1; i++)
		{
			for (int j = 1; j <= m - a + 1; j++)
			{
				if ((sum[i + a - 1][j + a - 1] - sum[i - 1][j + a - 1] -
					sum[i + a - 1][j - 1] + sum[i - 1][j - 1]) == a * a)
				{ 
					ans = a;
				}
			}
		}
		a++;
	}
	cout << ans << endl;
}