dede装修网站模板,制作图片的app免费,js 抽奖网站,wordpress栏目title目录
前言
问题描述
算法思路
定义方向 回溯算法
代码实现 前言 前面我发布了一篇关于迷宫问题的解决方法#xff0c;是通过栈的方式来解决这个问题的#xff08;链接#xff1a;经典算法-----迷宫问题#xff08;栈的应用#xff09;-CSDN博客#xff09;#xff…目录
前言
问题描述
算法思路
定义方向 回溯算法
代码实现 前言 前面我发布了一篇关于迷宫问题的解决方法是通过栈的方式来解决这个问题的链接经典算法-----迷宫问题栈的应用-CSDN博客但是这个方法只可以找到一条路径那么今天我们就进一步去讲解迷宫问题通过回溯算法来找到全部的路径下面就一起来看看吧
问题描述 给定一个迷宫指明起点和终点找出从起点出发到终点的有效可行路径就是迷宫问题maze problem。迷宫可以以二维数组来存储表示。0表示通路1表示障碍。注意这里规定移动可以从上、下、左、右四方方向移动求走出迷宫的全部路径 #define m 4
#define n 4int maze[m 2][n 2] {{1, 1, 1, 1, 1, 1},{1, 0, 0, 0, 1, 1},{1, 0, 1, 0, 0, 1},{1, 0, 0, 0, 1 ,1},{1, 1, 0, 0, 0, 1},{1, 1, 1, 1, 1, 1}}; 算法思路
定义方向 同样的每走到一个位置就要想该往哪一个方向去走所以有东南西北这4个方向每次往一个方向走之后就标记好当前方向和当前位置然后同样的去进行分享的试探当走到没路走的时候就进行原路返回。方向的定义如下 //试探方向存储结构
typedef struct {int xx, yy;
}Direction;
//东南西北
Direction dire[4] { {0,1},{1,0},{0,-1},{-1,0} }; 回溯算法 回溯计算机算法回溯法也称试探法它的基本思想是从问题的某一种状态初始状态出发搜索从这种状态出发所能达到的所有“状态”当一条路走到“尽头”的时候不能再前进再后退一步或若干步从另一种可能“状态”出发继续搜索直到所有的“路径”状态都试探过。这种不断“前进”、不断“回溯”寻找解的方法就称作“回溯法”。递归回溯由于回溯法是对解空间的深度优先搜索找到结果或者没找到结果就原路返回去找下一条路。可以看出回溯算法是一种暴力算法就是彻彻底底的一个一个找找得到就走找不到就回去。 对于本期的迷宫问题我们要想找到全部的路径就最好去用回溯算法也就是一个一个找毕竟实际情况走迷宫也是如此在不知道的情况下也只能去一个一个找。对于本题我们可以这样子走每走一个地方就把这个地方标记为-1表示已经走过当遇到死路的时候就返回上一个位置然后换一个方向来走直到换到可以走得通的方向走完这条路的话当前走完的路所有坐标都标记为-1我们就一直回溯换方向到其他方向能走的位置直到整个地图全部能走的路都标记为-1就结束回溯递归。 代码实现
#includestdio.h
#define m 4
#define n 4//试探方向存储结构
typedef struct {int xx, yy;
}Direction;
//东南西北
Direction dire[4] { {0,1},{1,0},{0,-1},{-1,0} };typedef struct node {int x, y;
}Node;
typedef struct path {Node data[100];//标记路径位置的数组int count;//统计节点
}Path;//输出路径
void print(Path p, int* N) {*N 1;printf(第%d条路径:\n, *N);for (int i 0; i p.count; i) {printf((%d,%d)-, p.data[i].x, p.data[i].y);}printf(Printover!\n\n);
}void find_path(int maze[][n2], int* N, int x, int y, int endx, int endy, Path p) {//如果走到终点的时候if (x endx y endy) {maze[x][y] -1;//把终点位置存入到路径去p.data[p.count].x x;p.data[p.count].y y;p.count;print(p, N);//输出路径//走完了就回到上一个位置然后换方向走return;}else {//如果当前位置为0也就是能走的话if (maze[x][y] 0) {int di 0;while (di 4) {//4个方向都进行试探//储存当前位置p.data[p.count].x x;p.data[p.count].y y;p.count;//标记为-1表示已经走过maze[x][y] -1;int i, j;//改变方向i x dire[di].xx;j y dire[di].yy;find_path(maze, N, i, j, endx, endy, p);//递归进入到下一个位置//回溯回到上一个位置继续操作//当前位置给抹除掉p.count--;maze[x][y] 0;di;//改变方向}}//不能走的话就返回回到上一个位置elsereturn;}
}int main() {int maze[m 2][n 2] {{1, 1, 1, 1, 1, 1},{1, 0, 0, 0, 1, 1},{1, 0, 1, 0, 0, 1},{1, 0, 0, 0, 1 ,1},{1, 1, 0, 0, 0, 1},{1, 1, 1, 1, 1, 1}};Path mp;mp.count 0;int N 0;find_path(maze, N, 1, 1, m, n, mp);
}
结果如下 以上就是本期的全部内容了我们下次见
分享一张壁纸
