解题思路:
bfs。
先强调一点,题目是先输入的列数,后输入的行数,不要搞反了。
①求出所给矩阵的和,如果和为奇数,无法分割。如果和为偶数,进行下一步。
②从第0行第0列开始进行深度搜索。如果搜索到某一个数值时,和为矩阵和的一半,则对最小格子数进行比较,更新。
最后输出答案即可
注意事项:
参考代码:
from cmath import inf def dfs(x,y,now,cnt): #四个参数分别为当前点的x坐标,y坐标,到当前点的和,到当前点包含的格子数 global n,m,Marix,Visit,sum_num,minnum if now > sum_num: return if now == sum_num: if cnt < minnum: minnum = cnt return D = [(-1,0),(1,0),(0,-1),(0,1)] for i in range(4): #上下左右 x_now = x+D[i][0] y_now = y+D[i][1] if (0<= x_now <= n-1) and (0<= y_now <= m-1) and Visit[x_now][y_now]: Visit[x_now][y_now] = 0 dfs(x_now,y_now,now+Marix[x_now][y_now],cnt+1) Visit[x_now][y_now] = 1 if __name__ == '__main__': m,n = map(int,input().strip().split()) Marix = [[int(j) for j in input().strip().split()] for i in range(n)] #记录矩阵 Visit = [[1 for j in range(m)] for i in range(n)] #访问数组 sum_num = 0 for i in range(n): #求矩阵和 sum_num = sum_num + sum(Marix[i]) minnum = inf if sum_num % 2 == 1: print(0) else: sum_num = sum_num//2 Visit[0][0] = 0 dfs(0,0,Marix[0][0],1) #进入搜索 if minnum == inf: print(0) else: print(minnum)
0.0分
1 人评分
母牛的故事 (C语言代码)浏览:1721 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:665 |
WU-蓝桥杯算法提高VIP-企业奖金发放 (C++代码)浏览:1191 |
WU-printf基础练习2 (C++代码)浏览:2008 |
2005年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:601 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:870 |
C二级辅导-统计字符 (C语言代码)浏览:484 |
前10名 (C语言代码)浏览:741 |
第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略浏览:1149 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:452 |