1834: 蓝桥杯2016年第七届真题-路径之谜(3.14)

解题思路:常规的DFS+剪枝:看到题目说求路径,第一反应就是深搜或者动态规划

注意事项:这个网站是可以ac的,但我在蓝桥杯提交了一下,发现第二个测试点居然是错误,我没开vip不知道为啥,都遍历全可能了还会错误???有知道的烦请@我一下

后续有两个测试点会超时
优化--不用额外数组存储行列经过次数,直接在原次数的基础上做减法,省去每次回溯复制数组的时间,剪枝条件改为<0就continue,.可能可以在官网ac?
参考代码:

# 暴力回溯+剪枝
def dfs(position, r_c, pas):
    global ans
    if position == (n - 1, n - 1):#到达右下角退出
        if r_c[0] == c_count and r_c[1] == r_count:
            ans = pas.copy() # 此处必须用copy,否则会返回0,我估计是python将pas回溯到了输入时的状态,赋值只赋值了一个引用
        return
    else:
        for each in directions:#遍历上左右的走法
            dx = position[0] + each[0]
            dy = position[1] + each[1]
            if 0 <= dx < n and 0 <= dy < n and not matrix[dx][dy]:
                r_c[0][dy] += 1 #将对应行和列的经过次数+1
                r_c[1][dx] += 1
                if r_c[0][dy] > c_count[dy] or r_c[1][dx] > r_count[dx]: # 若大于要求的次数就直接跳过,进行下一个方向
                    r_c[0][dy] -= 1
                    r_c[1][dx] -= 1
                    continue
                matrix[dx][dy] = 1 
                pas.append((dx, dy)) # 经过哪些坐标
                dfs((dx, dy), r_c, pas)
                r_c[0][dy] -= 1
                r_c[1][dx] -= 1
                matrix[dx][dy] = 0
                pas.pop()


n = int(input().strip())
c_count = list(map(int, input().strip().split()))
r_count = list(map(int, input().strip().split()))
ans = []
matrix = [[0 for _ in range(n)] for _ in range(n)]  # 是否走过坐标
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
r_c = [[0 for _ in range(n)] for _ in range(2)]  # 行和列的经过的次数
r_c[0][0] += 1 # 经过(0,0)
r_c[1][0] += 1
dfs((0, 0), r_c, [(0, 0)])
for each in ans:
    print(each[0] * n + each[1], end = " ")