大连网站建设特色,新任上海市领导调整公示,做床上用品网站,中国国家数据统计网#x1f483;#x1f3fc; 本人简介#xff1a;男 #x1f476;#x1f3fc; 年龄#xff1a;18 #x1f4d5; ps:七八天没更新了欸#xff0c;这几天刚搞完元宇宙#xff0c;上午一直练#x1f697;#xff0c;下午背四级单词和刷题来着#xff0c;还在忙一些学弟… 本人简介男 年龄18 ps:七八天没更新了欸这几天刚搞完元宇宙上午一直练下午背四级单词和刷题来着还在忙一些学弟学妹录制视频和准备开学一些事一直没空出时间来等 20号练完车也马上开学了QAQ。不过今天倒是空出来一些时间恰好这几天学到了dfs原理和例题都很棒谨以此篇作为学后的回顾总结 文章目录1. dfs算法原理1.1 dfs思想1.2 与递归区别1.3 举例说明2. 经典例题——迷宫游戏2.1 题干信息2.2 整体思路2.3 细分拆解①判断迷宫终点记录所走路径②完善搜索与回溯处理数组边界③找寻迷宫起点打印结束路径2.4 总体代码展示2.5 测试样例2.6 代码优化最后感谢大家支持u ^ _ ^1. dfs算法原理
1.1 dfs思想 深度优先搜索简称dfs简单讲就是一个搜索算法。 深搜是按照深度优先的方式进行搜索通俗来讲就是一条路走到黑和不撞南墙不回头。注意这里的搜索并不是我们平时在文件上或网络上查找信息而是通过一种穷举的方式把所有可行的方案都列举出来不断去尝试直到找到问题的解。具体来讲dfs可以将“问题状态空间”看做一棵搜索树深度优先就是从树根一直往下搜遇到不可解就回溯往其它方向继续向下扩展像子集和和全排列问题还有N皇后问题都可以深度优先搜索算法解决它是一种暴力解决NP问题的非常直观的方法。总的来说DFS 用于找所有解的问题它的空间效率高而且找到的不一定是最优解必须记录并完成整个搜索故一般情况下深搜需要非常高效的剪枝剪枝的概念请百度。
1.2 与递归区别
深搜是一种算法注重的是思想而递归是一种基于编程语言的实现方式。深搜可以用递归实现也就是说递归是我们用计算机编程语言实现深搜算法的手段。
1.3 举例说明 如下图灰色代表墙壁绿色代表起点红色代表终点规定每次只能走一步且只能往下或右走。求一条绿色到红色的最短路径。例子来源于这里 用dfs来讲就是先从绿点开始找准一个方向并沿这个方向一直遍历如果遇到障碍物不能继续遍历就回溯返回上一个节点直到找到终点为止。 2. 经典例题——迷宫游戏 都学了这么多了。我们不妨来玩一个迷宫游戏巩固一下所学的算法【迷宫如图下所示】 最短的解法如下图所示【大家答对了嘛】 2.1 题干信息
我们用一个二维字符数组来表示图画的迷宫。
S**.
....
***T其中S表示起点T表示终点*表示墙壁.表示平地。你需要从S出发走到T每次只能向上下左右相邻的位置移动一位不能走出地图也不能穿过墙壁每个点只能通过一次。用x表示你所要走的路线。
2.2 整体思路
我们从起点S开始每走一步需要对上下左右一个方向一个方向地尝试如果沿着某个方向不能走到终点我们就要原路返回继续尝试其他方向直到走出迷宫。这是一种最朴素的走迷宫方式虽然效率也许比较低但如果迷宫有解就一定能走出终点。上面说的这种走法就对应着今天学习的dfs算法。首先找到起点s,走到每个点时按照左、下、右、上的顺序尝试。每走到下一个点以后我们把这个点当做起点S继续按顺序尝试。如果某个点上下左右四个方向都尝试过便回到走到这个点之前的点这一步我们称之为回溯。继续尝试其他方向。直到所有点都尝试过上下左右四个方向。这就好比你自己去走这个迷宫你也要一个方向一个方向的尝试着走如果这条路不行就回头尝试下一条路dfs 的思想和我们直观的想法很类似。只不过接下来我们需要用程序来完成这个过程。
2.3 细分拆解
第一步前的输入地图和变量设置就不详细讲了直接看代码即可
#includeiostream
#includestdio.h
using namespace std;
int n, m;
char pos[150][150]; //判断走没走过
bool trace[150][150]; //显示路径int main() {//输入地图cin n m;for (int i 1; i n; i) {for (int j 1; j m; j) {cin pos[i][j];}}return 0;
}
①判断迷宫终点记录所走路径
首先确定边界条件当走到字符T时我们找到了终点从而结束搜索。所以边界条件判断为pos[x][y] T。其次为了防止走回头路我们需要标记当前这个路径已走过即当前这个点已走过所以我们需要用trace[x][y]数组来做标记为了显示出路径走过的点我们用字符x表示。
bool dfs(int x, int y) {if (pos[x][y] T) { //找到终点返回truereturn true;}trace[x][y] 1; //若找不到则trace数组标记为1表示已走过pos[x][y] x; //用pos显示最后的路径
}②完善搜索与回溯处理数组边界
结束操作处理好后就要开始真正的搜索了。假设现在我们坐标为(x, y),分别遍历该坐标的上下左右位置选择好依次进行方向的顺序后一个方向一个方向进行访问如果某一方向能走到终点则返回true。在上下左右遍历时我们要考虑数组元素是否越界此时我们就需要一个bool类型的check_in()函数进行判断。注意判断移动后位置能走的3个条件【缺一不可】 ①没越界在地图内②这个位置不是障碍物*可以走到③该位置之前没走过
bool check_in(int x, int y) { // 判断数组是否越界return (x 0 x n y 0 y m); //这里表示的是如果()里为真则返回true否则返回false
}bool dfs(int x, int y) {if (pos[x][y] T) { //找到终点返回truereturn true;}trace[x][y] 1; //若上下左右都找不到则trace数组标记为1表示已走过pos[x][y] x; //用pos显示最后的路径int tx x - 1, ty y; //假设先往上走if (check_in(tx, ty) pos[tx][ty] ! * !trace[tx][ty]) { //能移动到该位置的条件有三个①没越界在地图内 ②这个位置不是障碍物*可以走到 ③该位置之前没走过if (dfs(tx, ty)) { //对移动后位置进行判断是不是终点如果是返回true如果不是在对其上下左右判断。return true;}}tx x, ty y - 1; //如果往上走行不通则选择向左走if (check_in(tx, ty) pos[tx][ty] ! * !trace[tx][ty]) {if (dfs(tx, ty)) {return true;}}tx x 1, ty y; //如果往左走行不通则选择向下走if (check_in(tx, ty) pos[tx][ty] ! * !trace[tx][ty]) {if (dfs(tx, ty)) {return true;}}tx x , ty y 1; //如果往下走行不通则选择向右走if (check_in(tx, ty) pos[tx][ty] ! * !trace[tx][ty]) {if (dfs(tx, ty)) {return true;}}pos[x][y] .; // 如果一个位置的上下左右都走不了则取消该位置的路径进行回溯回溯过程把之前已标记的x改回.trace[x][y] 0;//只找可行路线的话trace可改可不改。但如果找全部解则需要恢复return false;
}大家有没有发现判断上下左右是否可行时主题代码是不是都是一样的欸所以大家可以想一下能怎么去优化一下嘛在这里我卖个关子咱们后面马上讲 ③找寻迷宫起点打印结束路径
我们费心费力地把迷宫主体的dfs的函数写完了但我们该从哪开始呢结束条件如何设置呢
int main() {//输入地图cin n m;for (int i 1; i n; i) {for (int j 1; j m; j) {cin pos[i][j];}}cout ---------------------------------------- endl;//找寻起点int x , y ; //定义xy用于保存迷宫起点时的位置for (int i 1; i n; i) {for (int j 1; j m; j) {if (pos[i][j] S) {x i, y j;}}}if (dfs(x, y)) { //如果能找到终点则打印迷宫显示其路径cout 鼠鼠我欸已到达终点啦路线如下: endl;for (int i 1; i n; i) {for (int j 1; j m; j) {cout pos[i][j];} cout endl;}}else {cout 鼠鼠我欸走不出去啦awa endl;}return 0;
}2.4 总体代码展示
#includeiostream
#includestdio.h
using namespace std;int n, m;
char pos[150][150]; //判断走没走过
bool trace[150][150]; //显示路径bool check_in(int x, int y) { // 判断数组是否越界return (x 0 x n y 0 y m); //这里表示的是如果()里为真则返回true否则返回false
}bool dfs(int x, int y) {if (pos[x][y] T) { //找到终点返回truereturn true;}trace[x][y] 1; //若上下左右都找不到则trace数组标记为1表示已走过pos[x][y] x; //用pos显示最后的路径int tx x - 1, ty y; //假设先往上走if (check_in(tx, ty) pos[tx][ty] ! * !trace[tx][ty]) { //能移动到该位置的条件有三个①没越界在地图内 ②这个位置不是障碍物*可以走到 ③该位置之前没走过if (dfs(tx, ty)) { //对移动后位置进行判断是不是终点如果是返回true如果不是在对其上下左右判断。return true;}}tx x, ty y - 1; //如果往上走行不通则选择向左走if (check_in(tx, ty) pos[tx][ty] ! * !trace[tx][ty]) {if (dfs(tx, ty)) {return true;}}tx x 1, ty y; //如果往左走行不通则选择向下走if (check_in(tx, ty) pos[tx][ty] ! * !trace[tx][ty]) {if (dfs(tx, ty)) {return true;}}tx x , ty y 1; //如果往下走行不通则选择向右走if (check_in(tx, ty) pos[tx][ty] ! * !trace[tx][ty]) {if (dfs(tx, ty)) {return true;}}pos[x][y] .; // 如果一个位置的上下左右都走不了则取消该位置的路径进行回溯回溯过程把之前已标记的x改回.trace[x][y] 0;//只找可行路线的话trace可改可不改。但如果找全部解则需要恢复return false;
}
int main() {//输入地图cin n m;for (int i 1; i n; i) {for (int j 1; j m; j) {cin pos[i][j];}}cout ---------------------------------------- endl;//找寻起点int x , y ; //定义xy用于保存迷宫起点时的位置for (int i 1; i n; i) {for (int j 1; j m; j) {if (pos[i][j] S) {x i, y j;}}}if (dfs(x, y)) { //如果能找到终点则打印迷宫显示其路径cout 鼠鼠我欸已到达终点啦路线如下: endl;for (int i 1; i n; i) {for (int j 1; j m; j) {cout pos[i][j];} cout endl;}}else {cout 鼠鼠我欸走不出去啦awa endl;}return 0;
}2.5 测试样例 2.6 代码优化
前面提到我们在对下一位置进行上下左右判断时需要写四个主体相同的代码。为了减少代码量我们不妨写一个循环用一个二维数组依次表示四个方向进而进行判断。
int dir[4][2] { { -1 , 0 } , { 0 , -1 } , { 1 , 0 } , { 0 , 1 } };
// 按逆时针依次表示 向上 向左 向下 向右
//第一个数表示x(行)变化第二个表示y(列)变化
bool dfs(int x, int y) {if (dfs(x, y) T) {return true;}trace[x][y] 1;pos[x][y] x;for (int i 1; i 4; i) { //1、2、3、4依次表示上、左、下、右int tx x dir[i][0]; //表示x加上第几个方向的第1个数即行变化int ty y dir[i][1]; //表示x加上第几个方向的第2个数即列变化if (check_in(tx, ty) pos[tx][ty] ! * !trace[tx][ty]) {if (dfs(tx, ty)) {return true;}}}pos[x][y] .; // 如果一个位置的上下左右都走不了则取消该位置的路径进行回溯回溯过程把之前已标记的x改回.trace[x][y] 0;//只找可行路线的话trace可改可不改。但如果找全部解则需要恢复
}优化后代码
#includeiostream
#includestdio.h
using namespace std;int n, m;
char pos[150][150]; //判断走没走过
bool trace[150][150]; //显示路径int dir[4][2] { { -1 , 0 } , { 0 , -1 } , { 1 , 0 } , { 0 , 1 } };
// 按逆时针依次表示 向上 向左 向下 向右
//第一个数表示x(行)变化第二个表示y(列)变化bool check_in(int x, int y) { // 判断数组是否越界return x 0 x n y 0 y m; //这里表示的是如果()里为真则返回true否则返回false
}bool dfs(int x, int y) {if (dfs(x, y) T) {return true;}trace[x][y] 1;pos[x][y] x;for (int i 1; i 4; i) { //1、2、3、4依次表示上、左、下、右int tx x dir[i][0]; //表示x加上第几个方向的第1个数即行变化int ty y dir[i][1]; //表示x加上第几个方向的第2个数即列变化if (check_in(tx, ty) pos[tx][ty] ! * !trace[tx][ty]) {if (dfs(tx, ty)) {return true;}}}pos[x][y] .; // 如果一个位置的上下左右都走不了则取消该位置的路径进行回溯回溯过程把之前已标记的x改回.trace[x][y] 0;//只找可行路线的话trace可改可不改。但如果找全部解则需要恢复}int main() {//输入地图cin n m;for (int i 1; i n; i) {for (int j 1; j m; j) {cin pos[i][j];}}cout ---------------------------------------- endl;//找寻起点int x , y ; //定义xy用于保存迷宫起点时的位置for (int i 1; i n; i) {for (int j 1; j m; j) {if (pos[i][j] S) {x i, y j;}}}if (dfs(x, y)) { //如果能找到终点则打印迷宫显示其路径cout 鼠鼠我欸已到达终点啦路线如下: endl;for (int i 1; i n; i) {for (int j 1; j m; j) {cout pos[i][j];} cout endl;}}else {cout 鼠鼠我欸走不出去啦awa endl;}return 0;
}
最后感谢大家支持u ^ _ ^ 如果感觉这篇文章对你有帮助的话不妨三连支持下十分感谢(✪ω✪)。 printf(点个赞吧*^*);cout 收藏一下叭o_o;System.out.println(评论一下吧^_^);print(关注一下叭0-0)
