A38905. （注.input()输入函数的括号中不允许添加任何信息）编程实现有一个N*M的矩阵方格，其中有些方格中有奖品，有些方格中没有奖品。小蓝需要从N*M的矩阵中选择一个方形区域，如果所选的正方形区域的一条对角线方格中都有奖品，其他方格都没有奖品，就会获得所选区域中的所有奖品，否则不能获得奖品。当给出N和M的值，及N*M的矩阵方格中摆放的奖品情况例如：N=5，M=6，奖品情况如下：选择上图红色正…
填空题
困难
知识点
题目描述
题目描述
（注.input()输入函数的括号中不允许添加任何信息）
编程实现
有一个N*M的矩阵方格，其中有些方格中有奖品，有些方格中没有奖品。小蓝需要从N*M的矩阵中选择一个方形区域，如果所选的正方形区域的一条对角线方格中都有奖品，其他方格都没有奖品，就会获得所选区域中的所有奖品，否则不能获得奖品。
当给出N和M的值，及N*M的矩阵方格中摆放的奖品情况
例如：N=5，M=6，奖品情况如下：
选择上图红色正方形区域，可以获得最多的4个奖品。
输入描述
第一行输入两个整数N和M（1≤N≤100，1≤M≤100），N表示矩阵的行数，M表示矩阵的列数，两个整数之间一个空格隔开
接下来输入N行，每行包括M个0或者1（0表示方格中没有奖品，1表示方格中有奖品），0或者1之间一个空格隔开
输出描述
输出一个整数，表示最多可获得的奖品数
样例输入
5 6
1 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
0 1 0 0 0 1
1 0 1 0 0 0样例输出
4参考答案
n, m = map(int, input().split(' '))
ls = []
for i in range(n):
ls.append([int(i) for i in input()[::2]])
def SUM(ls, start_i, start_j, r, c):
sum_ = 0
for i in range(start_i, r + 1):
sum_ += sum(ls[i][min(start_j, c):max(start_j, c) + 1])
return sum_
def dfsR(ls, start_i, start_j, i, j):
if i >= n or j >= m or ls[i][j] == 0:
return 0
elif SUM(ls, start_i, start_j, i, j) != i - start_i + 1:
return 0
else:
return dfsR(ls, start_i, start_j, i + 1, j + 1) + 1
def dfsL(ls, start_i, start_j, i, j):
if i >= n or j < 0 or ls[i][j] == 0:
return 0
elif SUM(ls, start_i, start_j, i, j) != i - start_i + 1:
return 0
else:
return dfsL(ls, start_i, start_j, i + 1, j - 1) + 1
res = 0
for i in range(n):
for j in range(m):
if ls[i][j] == 1:
start_i, start_j = i, j
res_r = dfsR(ls, start_i, start_j, i, j)
res_l = dfsL(ls, start_i, start_j, i, j)
res = max(res_r, res_l, res)
print(res)
上一题
下一题