设计思路
先通过三个题目来理解dfs
- 迷宫1:迷宫是否有解
- 迷宫2:迷宫解的数量
- 迷宫3:
- 求出最短路径的值
- 输出所有解的路径
通过迷宫1,你需要理解下面的概念
- dfs就是递归
- 前进与回溯
- 什么是状态
- 对于迷宫来说状态就是,通过数据的记录,你可以确定你当前所处的迷宫的位置,以及走过的点
- 如何表示走迷宫的状态
- 位置
- 走过的点
- 为什么位置是dfs的参数,而走过的点,不能作为dfs的参数
- dfs的本质就是在树上的行走,而每树上的每个点都代表一种状态
通过迷宫2,你需要理解下面的概念
- 什么是现场
- 如何设置与恢复现场
- 为什么不会导致迷宫走重复的路
- 设置与恢复现场
通过迷宫3,你需要理解下面的概念
- 什么是栈
- 栈的操作
- 递归本质就是在栈上的操作
- 怎么利用递归的栈来记录走过的路径
- 怎么求最短路径的值
两个新的题目
- 狼羊菜
- 酒的平分
巩固学习
- 状态的表示
- 状态之间的迁移
这两个题目为后面的图论与DP打下基础
练习
- 八皇后
- kkkk 抱佛脚