大良营销网站建设市场,wordpress 房产,使用最佳搜索引擎优化工具,erp系统一套大概多少钱最大正方形
题目描述
在一个 n m n\times m nm 的只包含 0 0 0 和 1 1 1 的矩阵里找出一个不包含 0 0 0 的最大正方形#xff0c;输出边长。
输入格式
输入文件第一行为两个整数 n , m ( 1 ≤ n , m ≤ 100 ) n,m(1\leq n,m\leq 100) n,m(1≤n,m≤100)#xff0c;接…最大正方形
题目描述
在一个 n × m n\times m n×m 的只包含 0 0 0 和 1 1 1 的矩阵里找出一个不包含 0 0 0 的最大正方形输出边长。
输入格式
输入文件第一行为两个整数 n , m ( 1 ≤ n , m ≤ 100 ) n,m(1\leq n,m\leq 100) n,m(1≤n,m≤100)接下来 n n n 行每行 m m m 个数字用空格隔开 0 0 0 或 1 1 1。
输出格式
一个整数最大正方形的边长。
样例 #1
样例输入 #1
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1样例输出 #1
2题解
这道题AcWing、洛谷和leetCode都有只是输入还有输出的些微区别这里只提供洛谷的Python代码思路是一样的。
这道题其实不难看出来可以用动态规划做但是我做这道题的时候是有人要求我先用前缀和做一遍了所以我这里提供两种思路
1、前缀和
这道题前缀和做法其实很简单就是看我们想要通过求的正方形的前缀和来求该正方形的面积如果求出来的面积与正方形边长平方相等那么这个边长的正方形就满足要求
if 通过前缀和求的面积 正方形边长 ** 2return True怎么通过前缀和求矩形面积呢我们可以通过下面公式来计算 设 i 2 , j 2 i_2, j_2 i2,j2 为矩形右下角 i 1 , j 1 i 2 − l e n S q u a r e 1 , j 2 − l e n S q u a r e 1 i_1, j_1 i_2 - lenSquare 1, j_2 - lenSquare 1 i1,j1i2−lenSquare1,j2−lenSquare1 为矩形左上角那么通过前缀和求矩形面积公式为 S i z e ( S q u a r e ) P r e f i x [ i 2 ] [ j 2 ] − P r e f i x [ i 1 − 1 ] [ j 2 ] − P r e f i x [ i 2 ] [ j 1 − 1 ] P r e f i x [ i 1 − 1 ] [ j 1 − 1 ] Size(Square) Prefix[i_2][j_2] -Prefix[i_1-1][j_2]-Prefix[i_2][j_1-1] Prefix[i_1-1][j_1-1] Size(Square)Prefix[i2][j2]−Prefix[i1−1][j2]−Prefix[i2][j1−1]Prefix[i1−1][j1−1]
下面这张图为上图的前缀和矩阵 那么穷举求出每种正方形边长的情况我们就可以得到可能的正方形边长
欸别急直接穷举正方形边长还是慢了正方形边长是从小到大穷举的我们可以使用二分来加速对边长的举证
if mid正方边长满足要求:我们去找是否存在更大的边长满足要求left mid 1
else:mid长度都不符合要求的直接去找更小的边长了 right mid - 1最后得出Python代码(时间复杂度为 O ( N 2 l o g 2 N ) O(N^2log_2N) O(N2log2N))
def judge(lenEdge, Prefix):global N, Mfor i in range(lenEdge, N1):for j in range(lenEdge, M1):if Prefix[i][j] - Prefix[i-lenEdge][j] - Prefix[i][j-lenEdge] Prefix[i-lenEdge][j-lenEdge] lenEdge**2:return Trueelse:return FalseN, M map(int, input().strip().split())
A [[0 for _ in range(M1)]]
for i in range(1, N1):tmp [0]tmp.extend(map(int, input().strip().split()))A.append(tmp)
Prefix [[0 for _ in range(M1)] for _ in range(N1)]
for i in range(1, N1):for j in range(1, M1):Prefix[i][j] Prefix[i-1][j] Prefix[i][j-1] - Prefix[i-1][j-1] A[i][j]
left, right 0, min(N, M)
ans 0
while left right:mid (left right) // 2if judge(mid, Prefix):ans max(ans, mid)left mid 1else:right mid - 1
print(ans)2、动态规划法
动态规划法的想法更容易想到这里用图来说明一下 定义 i , j i,j i,j为正方形的左下角坐标且 d p [ i ] [ j ] dp[i][j] dp[i][j]存的是该正方形的边长 ( 4 , 4 ) (4,4) (4,4)代表的正方形的边长可以从红色、蓝色、绿色 ( 3 , 3 ) , ( 3 , 4 ) , ( 4 , 3 ) (3,3),(3,4),(4,3) (3,3),(3,4),(4,3)三种颜色的正方形来得出 可以看出来黑色框出正方形边长为11 2通过多画图推导得出下面的公式 d p [ i ] [ j ] m i n ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j − 1 ] ) 1 dp[i][j] min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) 1 dp[i][j]min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])1
时间复杂度为 O ( N 2 ) O(N^2) O(N2)
N, M map(int, input().strip().split())
A [[0 for _ in range(M)]] [[0] list(map(int, input().strip().split())) for _ in range(N)]
dp [[0 for _ in range(M1)] for _ in range(N1)]
ans 0
for i in range(1, N1):for j in range(1, M1):if A[i][j] 1:dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1ans max(ans, dp[i][j])
print(ans)
