蓝桥杯-剪格子（python实现）

一、题目描述

时间限制：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)