蓝桥杯 2013年第四届真题 剪格子
蓝桥杯 2013年第四届真题 剪格子
问题描述
如下图所示，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。
输出格式
输出一个整数，表示在所有解中，包含左上角的分割区可能包含的*小的格子数目。
样例输入1
3 3
10 1 52
20 30 1
1 2 3
样例输出1
3
样例输入2
4 3
1 1 1 1
1 30 80 2
1 1 1 100
样例输出2
10
解决：使用DFS算法搜索所有可能的划分
首先根据输入求得格子总值的半数half_sum，题目要求我们将所有格子划分为两个区域，每个区域的总值为half_sum。
定义dfs前进的四个方向，其横纵坐标分别用x_ori，y_ori表示。定义数组 visit 记录每个格子是否已被访问。
从[0,0]位置开始深度优先搜索。
深度优先搜索部分：
利用格子横纵坐标进行DFS。每次遍历上下左右四个方向，朝可以前进的方向迈进一步。
DFS过程中记录当前区域的格子总值total，若total>half_sum，则该划分失败，回溯；否则若total==half_sum，则说明得到一个有效划分。此时分为两种情况：
如果count=True，即正在划分*个区域（包含[0,0]的区域），则需要继续DFS划分第二个区域；
如果count=False，即正在划分第二个区域。若两个区域的格子总个数==m*n，说明找到了一个成功的划分，成功次数+1。
如果成功次数==0，则打印0，否则打印[0,0]格子所在区域的*小格子数。
n,m = map(int, input().split())
matrix = []
visit = [[True] * n for _ in range(m)]
total_sum = 0
for i in range(m):
l = [int(i) for i in input().split()]
total_sum += sum(l)
matrix.append(l)
half_sum = int(total_sum/2) # 格子总值的一半
x_ori = [1, 0, -1, 0] # 下 右 上 左
y_ori = [0, 1, 0, -1]
success = 0 # 记录成功次数
min_blocks = m*n # 记录*个格子所在区域的*少格子数
# 深度优先搜索，
# x,y表示当前搜索到的格子所在横纵坐标
# total表示当前搜索格子总值
# count=True表示需要记录区域格子数，为了计算*个格子所在区域的*少格子数。因此count=True也可以用来表示当前正在寻找*个区域还是第二个区域
# counter表示*个格子所在区域的格子数（只有count=True时需要计数）
# total_blocks用于记录两个区域的格子总数是否为m*n
def dfs(x, y, total, counter, total_blocks,count = True):
if total > half_sum: # 若当前区域的格子总值大于half_num则返回
return
if total == half_sum: # 找到一个区域
if count: # count=True表示正在寻找[0,0]格子所在区域，即*个区域，需要继续寻找下一个区域
#print(‘Find first 60!’)
for i in range(m): # 遍历寻找下一个起始点
for j in range(n):
if visit[i][j]:
dfs(i, j, matrix[i][j], counter, total_blocks+1, False) # count=False表明开始寻找下一个区域
elif total_blocks == m*n: # count=False，且total_blocks=m*n，说明找到了满足题目要求的两个区域
#print(‘Find second 60!’)
global success, min_blocks
success += 1
if min_blocks > counter: # 更新区域*小格子数
min_blocks = counter
return
for i in range(4): # 四个方向
x_new = x + x_ori[i]
y_new = y + y_ori[i]
if x_new < 0 or y_new<0 or x_new>=m or y_new>=n:
continue
if visit[x_new][y_new]:
visit[x_new][y_new] = False
if count:
dfs(x_new, y_new, total+matrix[x_new][y_new], counter+1, total_blocks+1, count)
else:
dfs(x_new, y_new, total+matrix[x_new][y_new], counter, total_blocks+1, count)
visit[x_new][y_new] = True
# 从[0,0]开始dfs
visit[0][0] = False
dfs(0, 0, matrix[0][0], 1, 1,True)
if success:
print(min_blocks)
else:
print(0)
