A38871. （注.input（）输入函数的括号中不允许添加任何信息）
填空题
困难
知识点
题目描述
题目描述
（注.input（）输入函数的括号中不允许添加任何信息）
时间限制：3000MS 内存限制：589824KB
编程实现
小明有一张N*M的方格纸，且部分小方格中涂了颜色，部分小方格还是空白。
给出N（2≤N≤30）和M（2≤M≤30）的值，及每个小方格的状态（被涂了颜色小方格用数字1表示，空白小方格用数字0表示），请帮助小明找出最大的矩形空白区域，并输出该矩形空白区域由多少个小方格组成。
例如：N=4，M=5，4*5的方格纸中每个小方格的状态如下图：
最大的空白区域由6个小方格组成（红色框区域）。
输入描述
第一行输入两个正整数N和M（2≤N≤30，2≤M≤30），分别表示方格纸的行数和列数，两个正整数之间以一个空格隔开
第二行开始输入N行，每行M个整数（整数为1或者0），1表示涂色方格，0表示空白方格，整数之间以一个空格隔开
输出描述
输出一个整数，表示最大矩形由多少个小方格组成（如果没有空白小方格，输出0）
样例输入
4 5
1 1 0 0 0
1 0 1 0 0
0 0 0 1 1
0 0 0 1 0
样例输出
6
参考答案
class stack(object): # 栈
def __init__(self):
self.__list = []
def is_empty(self):
return self.__list == []
def push(self, item):
self.__list.append(item)
def pop(self):
self.__list.pop()
def top(self):
if self.__list:
return self.__list[-1]
else:
return None
def size(self):
return len(self.__list)
def Max_s(lis):
st=stack()
max_=0
for i in range(len(lis)):
if st.is_empty() or lis[i]>lis[st.top()]:
st.push(i)
else:
while st.is_empty()==False and lis[i]<lis[st.top()]:
h=lis[st.top()]
st.pop()
if st.is_empty():
w= i
else :
w = i - 1 - st.top()
max_=max(max_,h*w)
st.push(i)
while st.is_empty()==False :
h=lis[st.top()]
st.pop()
if st.is_empty():
w= i
else :
w = i - 1 - st.top()
max_=max(max_,h*w)
return max_
n,m=map(int,input().split())
ls=[]
for i in range(n):
ls.append(list(map(int,input().split())))
max_n=0
lst=[0]*m
for i in range(n):
for j in range(m):
if ls[i][j]==0 :
lst[j] +=1
else :
lst[j]=0
max_n=max(max_n,Max_s(lst))
print(max_n)
上一题
下一题