蓝桥杯备赛：DFS算法详解与实战
蓝桥杯备赛：DFS算法详解与实战
坚持坚持！（解题步骤部分借鉴大佬们的代码，如有侵权请联系删除）
一、DFS例题
试题链接： 路径之谜
问题描述：小明冒充X星球的骑士，进入了一个奇怪的城堡。城堡里什么也没有，只是方形石头铺成的地面。假设城堡地面是n×n个方格。如图所示。
按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有n个靶子）
同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？有时是可以的，比如上图中的例子。本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
输入格式
第一行一个整数N（0<N<20），表示地面有N×N个方格。
第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）
输出格式
一行若干个整数，表示骑士路径。
为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号：0，1，2，3，……。
比如图中的方块编号为
输入样例
4
2 4 3 4
4 3 3 3
输出样例
0 4 5 1 2 3 7 11 10 9 13 14 15
问题分析
首先我们的初始位置为(1,1)，我们设置了两个列表dx，dy可以让其进行上下移动，并且每到一个新位置，就会把其北边和南边的箭拔掉。
check函数帮助我们判断该点是否到了出口，若到了出口判断墙上是否还有箭。若有，则回溯；若没有，则直接输出所有点的位置。（每个点的值可以用n*(x-1）+y-1表示）
pd函数帮助我们判断能否走到该点，即判断该点是否走过、横纵坐标有没跑出格子外、该点的北面和西面墙上还有没箭。
dfs函数对于每一个点，先check，再往上下左右走，并进行pd，若可行，则进行拔箭，存储该点（为最后print服务），记录走过该点。然后对其下一个位置进行dfs，若下一个位置各种路径都走不出去，则又返回到该点的位置，那我们需要进行场景复原，把墙上的箭插回去等，并继续遍历，朝其他方向走。
sys.exit()实现在print之后整个程序结束运行
代码示例
import os
import sys
def dfs(i, j):
global key, no, we
if pd(i, j):
return
else:
for _ in range(4):
ii = i + he[_]
jj = j + sh[_]
if check(ii, jj):
key[ii][jj] = 1
we[ii] -= 1
no[jj] -= 1
ls.append(ii * n + jj)
dfs(ii, jj)
key[ii][jj] = 0
we[ii] += 1
no[jj] += 1
del ls[-1]
def check(ii, jj):
global key, no, we
if ii < 0 or jj < 0 or ii >= n or jj >= n:
return False
elif key[ii][jj] == 1:
return False
elif we[ii] == 0 or no[jj] == 0:
return False
else:
return True
def pd(i, j):
global key, no, we, n
if i != n - 1 or j != n - 1:
return False
elif max(no) != 0 or max(we) != 0:
return False
else:
for _ in ls:
print(_, end=" ")
sys.exit()
if __name__ == "__main__":
n = int(input())
no = [int(_) for _ in input().split()]
we = [int(_) for _ in input().split()]
no[0] -= 1
we[0] -= 1
key = [[0] * n for _ in range(n)]
key[0][0] = 1
he = [-1, 0, 1, 0]
sh = [0, -1, 0, 1]
ls = [0]
dfs(0, 0)