蓝桥杯剪格子（python实现）

向右看齐 2022-11-12 09:48 180阅读 0赞

在b站看了大佬的讲解视频，觉得比较好理解，然后将它转换成了python可运行的代码

传送门[https://www.bilibili.com/video/BV1Ei4y187sQ?share\_source=copy\_web][https_www.bilibili.com_video_BV1Ei4y187sQ_share_source_copy_web]

不同的是 我是从0开始的，然后通过这段代码我也学会了一些用python表达的方式

# 输入两个整数
    m, n = list(map(int, input().split()))
    # 构建一个n * m的二维数组
    arr = []
    for i in range(n):
        arr.append(list(map(int, input().split())))
    # 初始化，纪录该格子是否被访问
    visited = [[0 for j in range(m)] for i in range(n)]
    sum = 0
    # 格子总数之和
    for i in range(n):
        for j in range(m):
            sum += arr[i][j]
    if sum % 2 == 0:
        sum = int(sum / 2)
    # 定义上下左右四个方向
    move = [[0, 1], [0, -1], [-1, 0], [1, 0]]
    # 最终格子对最小数目，设置初始值为无穷大
    res = float("inf")
    # 判断是否有答案的标记
    flag = False
    
    
    # 判断是否越界
    def judgeBorder(x, y):
        return 0 <= x <= n - 1 and 0 <= y <= m - 1
    
    
    # num代表当前已有格子的数目，now代表当前格子里的数字之和
    def dfs(x, y, num, now):
        global res
        global flag
        # 截止条件
        # 当目前格子数比sum还大时，以及格子数大于最终答案时，结束程序
        if now > sum or num >= res:
            return
        if sum == now:
            flag = True
            res = num
        # 搜索条件
        for i in range(4):
            tx = x + move[i][0]
            ty = y + move[i][1]
            # 确保路径在格子里，以及走没走过的路，才能上下左右进行搜索
            if judgeBorder(tx, ty) and not visited[tx][ty]:
                # 标记该点，证明该点已走过
                visited[tx][ty] = 1
                dfs(tx, ty, num + 1, now + arr[tx][ty])
                # 取消标记，回溯，当前的步骤不能对下步有影响
                visited[tx][ty] = 0
    
    
    visited[0][0] = 1
    dfs(0, 0, 1, arr[0][0])
    if flag:
        print(res)

[https_www.bilibili.com_video_BV1Ei4y187sQ_share_source_copy_web]: https://www.bilibili.com/video/BV1Ei4y187sQ?share_source=copy_web