DFS模板总结
常用剪枝与优化方法:
1、优化搜索顺序
2、排除等效冗余
3、可行性剪枝
4、最优性剪枝
def dfs(ax, ay):
if 剪枝1: ...
if 剪枝2: ...
...
if 剪枝n: ...
if finish():
pass#递归出口,当访问到“叶子节点”应该怎么做
for i in range(len(dx)):#扩展新点
x, y = ax + dx[i], ay + dy[i]
if 0 <= x < n and 0 <= y < m and not st[x][y]:#判断该点能不能走
st[x][y] = True#标记该点被走过
dfs(x, y)#扩展
st[x][y] = False#回溯
def main():
st[x][y] = True#标记起点被走过
dfs(x, y)#进入递归
st[x][y] = False#退出