M21577:（201911）护林员盖房子

matrix, implementation, http://cs101.openjudge.cn/practice/21577

在一片保护林中，护林员想要盖一座房子来居住，但他不能砍伐任何树木。现在请你帮他计算：保护林中所能用来盖房子的矩形空地的最大面积。

输入保护林用一个二维矩阵来表示，长宽都不超过20（即<=20）。第一行是两个正整数m,n，表示矩阵有m行n列。然后是m行，每行n个整数，用1代表树木，用0表示空地。

输出一个正整数，表示保护林中能用来盖房子的最大矩形空地面积。

样例输入

样例输出

提示

子矩阵边长可以为1，也就是说： 0 0 0 0 0 依然是一个可以盖房子的子矩阵。

【欧阳韵妍，2021年秋】感觉做这种矩阵题目最担心的是 for 循环太多了会超时，幸好这里用了 4 重也没有超时。这道题就是依次看看保护林中以每个空地为原点，向右向下能建多大的矩形。矩形竖向长度每向下拓宽一个单位（for k 循环），都需要重新通过 for h 循环看矩形横向长度能达到多长。这里有一个小点要注意：如果前一个长度中横向长度最长为 maxn（maxn≤n），那么下一个长度的横向长度肯定≤maxn，因为不能弄出：

python

# http://cs101.openjudge.cn/practice/21577
m, n = map(int, input().split())
L = [[int(x) for x in input().split()] for i in range(m)]
a = 1
for i in range(m):
    for j in range(n):
        if L[i][j] == 0:
            maxn = n #当k不断加上去时，能达到的h的最大长度
            for k in range(i, m): #竖着有多长
                for h in range(j, maxn): #横着有多长
                    if L[k][h] == 0:
                        a = max(a, (k-i+1)*(h-j+1))
                    else:
                        maxn = h
                        break
print(a)

思路：两遍扫描，第一遍相当于预处理。先遍历求出第 i 行第 j 列的格左相邻的 0 的个数。

然后再遍历，对第 i 行第 j 列的格，设定length和width两个属性，与其上方的格对比，求出最大的面积

python

#代码，参考 https://blog.csdn.net/coderwait/article/details/90215607

m, n = map(int, input().split())
a = []
a.append([0]*(n+2))
for i in range(m):
    a.append([0] + [int(x) for x in input().split()] + [0])
a.append([0]*(n+2))
    
for i in range(1, m+1):
    for j in range(1, n+1):
        if a[i][j] == 0:
            a[i][j] = a[i][j-1] + 1 #宽度累加
        else:
            a[i][j] = 0    #种树了的地方因为没办法算数字,记为0

# 遍历每一个位置，向上回溯的方式，求以该位置为最右下角的树群的最大值
ans = 0
width = 0
for i in range(1, m+1):
    for j in range(1, n+1):
        if a[i][j] == 0:
            continue
        
        width = a[i][j]     #设置为档期的宽度
        ans = max(ans, width*1);
        for k in range(i-1, 0, -1):
            if a[k][j] == 0:
                break       #如果搜到树，则说明不用再往上了
            else:
                width = min(a[k][j], width) #更新可以盖房子的宽度
                ans = max(ans, width * (i - k + 1)) 

print(ans)

【韩袭怡腾，2021年秋】因为说是矩形，而且还是20×20 的，考虑到从每个点开始只往右下扩展的矩形数量是可求的，所以像这种比较小的数，直接brute force 完全没有问题，当然要注意循环的时候各个参数的取值。

python

m,n=map(int,input().split())
s=[[int(k)for k in input().split()]  for _ in range(m)]
area=0
for i in range(m):
    for j in range(n):
        if s[i][j]==0:
           for x in range(m-i):
              for y in range(n-j):
                  he=0
                  for k in range(x+1):
                      for l in range(y+1):
                          he+=s[i+k][j+l]
                  if he==0:
                      area=max(area,(x+1)*(y+1))
print(area)

【黄章毅，2021年秋】

python

n,m=map(int,input().split())
l=[[1]*(m+2)]+[[1]+[int(i) for i in input().split()]+[1] for j in 
range(n)]+[[1]*(m+2)]
ans=[]
for i in range(1,n+1):
    for j in range(1,m+1):
        for p in range(i,n+2):
            for q in range(j,m+2):
                for k in range(i,p+1):
                    if sum(l[k][j:q+1])!=0:
                        break
                else:
                    ans.append((p-i+1)*(q-j+1))
print(max(ans))

M21577:（201911）护林员盖房子 ​

M21577:（201911）护林员盖房子