妙先生

用户名：uq_57083779177

访问量：24902

签　名：

妙啊！

等　　级
排　　名	235
经　　验	6011
参赛次数	0
文章发表	73
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

[递归]母牛的故事-题解（Python代码）
浏览：271

蓝桥杯历届试题-蚂蚁感冒-题解（Python代码）
浏览：472

蓝桥杯2015年第六届真题-穿越雷区-题解（Python代码）
浏览：463

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

蓝桥杯2013年第四届真题-剪格子-题解(Python代码)

　　作者: 妙先生　　　　发表时间：2020-02-26 22:46:33 浏览：590　|　评论：2　

原题链接：蓝桥杯2013年第四届真题-剪格子

本题题意简单来说就是从坐标（1,1）格子开始找与自己相加等于总格子和一半的最少的格子数。使用DFS就可以解决。

思路：是将格子用列表套列表相当二维数组存储，然后再建立一个同样大小的数组来表示有没有被访问过。

代码如下：
```python
count = 100     #记录格子数
def DFS(n,m,map1,vis,sum,x,y,xx,yy,ant,sum0):
    """深搜"""
    global count
    if sum0 == sum//2 and count > ant:  #判断是否当前点的值为总和一半，是一半表示找到了一种方法
        count = ant     #count表示所有方法的最小格子数，ant表示当前方法的格子数
    for i in range(4):  #模拟当前坐标上下左右的方走
        dx = x + xx[i]
        dy = y + yy[i]
        if dx>=1 and dx<=m and dy>=1 and dy<=n and  not vis[dx][dy]:
            """dx，dy不能越界并且下一节点没被访问过"""
            vis[dx][dy] = True
            DFS(n,m,map1,vis,sum,dx,dy,xx,yy,ant+1,sum0+map1[dx][dy])  #满足条件就格子数加一，和加上当前格子数值
            vis[dx][dy] = False     #回溯

def main():
    global count
    m , n =map(int , input().split())
    map1 = [[0 for _ in range(m+2)]]+[[0]+list(map(int , input().split()))+[0] for i in range(n)] + [[0 for _ in range(m+2)]]   #生成图
    vis = [[False for i in range(m+2)] for _ in range(n+2)]     #记录每个点是否有没有被访问过
    vis[1][1] = True    #从坐标1,1开始所以直接令1,1为访问过
    xx = [0,1,0,-1]     #x方向的移动
    yy = [1,0,-1,0]     #y方向的移动
    sum , sum0= 0 , map1[1][1]  #sum用来记格子总和，sum0用来记录访问到当前节点的总和值
    for i in range(1,n+1):
        for j in range(1,m+1):
            sum += map1[i][j]
    if sum%2 == 1:  #如果总和为奇数这不可能会分为两相等的部分
        print(0)
        return
    DFS(n,m,map1,vis,sum,1,1,xx,yy,1,sum0)
    print(0) if count == 100 else print(count)  #如果count = 100则表示无法分割输出0，否则输出最小格子数

if __name__ == '__main__':
    main()
```
注释已经够清楚，如有问题欢迎留言，或私信。

0.0分

7 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

月初

请问一下为什么需要在map1上面增加一行和一列呀

2022-03-13 14:11:55

你

妙呀！在map1里增添一行和一列0， 就解决了一些特殊的情况。

2020-10-16 16:16:01

妙先生

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

【蟠桃记】（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

蓝桥杯2013年第四届真题-剪格子-题解(Python代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

多输入输出练习1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

【蟠桃记】（C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

字符逆序（C语言代码）

A+B for Input-Output Practice （C语言代码）

永远的丰碑（C语言代码）

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

妙先生

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

【蟠桃记】 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

蓝桥杯2013年第四届真题-剪格子-题解(Python代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

多输入输出练习1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

【蟠桃记】 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

字符逆序 （C语言代码）

A+B for Input-Output Practice （C语言代码）

永远的丰碑 （C语言代码）

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

【蟠桃记】（C语言代码）

　　评论区

【蟠桃记】（C语言代码）

字符逆序（C语言代码）

永远的丰碑（C语言代码）