时间限制:1.0s 内存限制:256.0MB
如下图所示,3 x 3 的格子中填写了一些整数。
±—*---±-+
|10* 1|52|
±-****–+
|20|30* 1|
*******–+
| 1| 2| 3|
±-±-±-+
我们沿着图中的星号线剪开,得到两个部分,每个部分的数字和都是60。
本题的要求就是请你编程判定:对给定的m x n 的格子中的整数,是否可以分割为两个部分,使得这两个区域的数字和相等。
如果存在多种解答,请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割,则输出 0。
输入:
程序先读入两个整数 m n 用空格分割 (m,n< 10)。
表示表格的宽度和高度。
接下来是n行,每行m个正整数,用空格分开。每个整数不大于10000。
输出:
输出一个整数,表示在所有解中,包含左上角的分割区可能包含的最小的格子数目。
样例输入
3 3 10 1 52 20 30 1 1 2 3
样例输出
3
主要思路是用深度优先搜索的方式搜索解空间,具体实现可以看注释。
(在解决许多问题时采用深度优先而不是宽度优先的原因有很多,如深度优先可以利用递归编写程序,代码更简单易懂;深度优先在搜索中可以剪枝;深度优先在搜索最优解时,可以将代价大于已知最优解的分支剪枝…)
"""h,w分别代表即将加入解的表中结点的第一、二个索引, res是加入结点前当前左上角区域已包含的格子数, cur是加入结点前左上角区域的和""" def dfs(h, w, res, cur): global m, n, ls, sum1, best, used # 将结点加入左上角区域 cur = cur+ls[h][w] res += 1 used[h][w]=1 if res<best: if cur == sum1: best = res elif cur< sum1: if h<n-1 and used[h+1][w]==0: dfs(h+1, w, res, cur) if h>0 and used[h-1][w]==0: dfs(h-1, w, res, cur) if w<m-1 and used[h][w+1]==0: dfs(h, w+1, res, cur) if w>0 and used[h][w-1]==0: dfs(h, w-1, res, cur) # 让结点还原未考虑状态 used[h][w]=0 """m,n接收输入,ls保存表格,used全局变量表示结点是否添加过,0未添加,1添加过 best用于保存搜索到的左上角最少格子数""" # while True: m, n = map(int, input().split()) ls = list() for i in range(n): ls.append(list(map(int, input().split()))) sum1 = sum(map(sum, ls)) # 若不能整除2则一定不存在解,若能整除则左上角区域和为sum1=sum1/2 if sum1%2!=0: print(0) else: sum1 = sum1//2 best = 100 used = [[0 for i in range(m)] for i in range(n)] dfs(0, 0, 0, 0) if best<100: print(best) else: print(0)