题目描述
如下图所示，3 x 3 的格子中填写了一些整数。
我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是 60。
本题的要求就是请你编程判定：对给定的 m×n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。
如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割，则输出 0。
输入描述
输入描述
程序先读入两个整数 m,n 用空格分割 (<10)(m,n<10)，表示表格的宽度和高度。
接下来是 n 行，每行 m 个正整数，用空格分开。每个整数不大于 10^4。
输出描述
在所有解中，包含左上角的分割区可能包含的最小的格子数目。
输入输出样例
示例
输入
3 3
10 1 52
20 30 1
1 2 3
输出
3
思路：分析题目我们需要先计算出所有格子数字的总和，然后从左上角选取相邻的格子，使其上面的数字之和是整个矩阵数字之和的1/2，并求出满足这个条件的最少格子。使用DFS搜索，然后做适当剪枝
def dfs(x,y,c,s):
#x,y是横纵坐标 c是取到的格子数量 s是取到的格子数字之和
global ans,sum_num#定义全局变量
if 2*s>sum_num: return#当目前所选的格子之和的二倍大于矩阵总和时，直接return进行剪枝
if 2*s==sum_num:#满足条件之后与之前满足条件的情况进行对比，求出最少格子
if ans>c and vis[0][0]==1:#必须得经过左上角的格子
ans =c
return
vis[x][y]=1#将坐标为[x][y]的格子标记为已经走过
dir = [(-1,0),(1,0),(0,-1),(0,1)]#用来计算相邻格子
for u,v in dir:
nx,ny=x+u,y+v#新的格子的坐标
if nx>=0 and nx<=n-1 and ny>=0 and ny<=m-1:#判断新格子是否还在矩阵中
if vis[nx][ny]==0:#如果新格子没有取到，则准备取，进行下一步回溯
dfs(nx,ny,c+1,s+mp[x][y]) #对新格子进行回溯，更新c（取到的格子数量），s（取到的数字之和）
vis[x][y]=0
m,n=map(int,input().split())
mp = []
for i in range(n):
mp.append(list(map(int,input().split())))
vis = [[0]*m for i in range(n)]#用来记录是否取到格子
sum_num = 0
for i in mp:
sum_num +=sum(i)#累加mp每行的值
ans = 1000000
dfs(0,0,0,0)
print(ans)
文章来源
您阅读本篇文章共花了：
发表评论