最大正方形

题目描述

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

输入格式

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

输出格式

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

样例输入

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

样例输出

2

算法1

(动态规划) $O(n^m)$

主要思想：

1.状态定义
f[i][j]表示以 [i][j]为结尾的最大正方形的最大变长

2.if(g[i][j]==1) - 初步判断当前节点是否为合法的节点
3.状态计算
f[i][j] =min( min(f[i-1][j],f[i][j-1]), f[i-1][j-1]) + 1;
f[i-1][j] 表示 包括 (i,j) 节点 向左连续 x个节点
f[i][j-1] 表示 包括 (i,j) 节点 向上连续 x个节点
f[i-1][j],f[i][j]等价于 从(i,j)节点 向左向上连续x个节点的合法格子

• 两个当中取小的为正方形的边长(细品)
• • 1 表示包括当前格子
• 最后枚举所有合法的方案中取最大值

时间复杂度

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 110 ;

#define int long long

int n,m;
int g[N][N];
int f[N][N];

signed main() {

	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
			cin>>g[i][j];

	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
		 {
		 	if(g[i][j]==1)  //当前节点是否为合法的节点
			 f[i][j] = min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;
			 
		 }
		
		int res=f[0][0];
		for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
		 res=max(res,f[i][j]);
		
		cout<<res;
		return 0;
		}