建网站需要那些工具,镇江疾控紧急提醒,最简单的html代码,网站分页导航这是《C算法宝典》算法篇的第08节文章啦~ 如果你之前没有太多C基础#xff0c;请点击#x1f449;专栏#xff1a;C语法入门#xff0c;如果你C语法基础已经炉火纯青#xff0c;则可以进阶算法#x1f449;专栏#xff1a;算法知识和数据结构#x1f449;专栏#xff… 这是《C算法宝典》算法篇的第08节文章啦~ 如果你之前没有太多C基础请点击专栏C语法入门如果你C语法基础已经炉火纯青则可以进阶算法专栏算法知识和数据结构专栏数据结构啦 目录
广搜走迷宫找最短路径
如何找到最短路径
问题建模
如何表示迷宫地图等信息呢
如何表示每次移动的过程
如何实现搜索的过程呢
问题参考程序
广度优先搜索模板
训练森林救援
参考代码 广搜走迷宫找最短路径
现在有一个4*4的迷宫小知在迷宫的左上角迷宫出口在右下角小知体力有限他希望尽快走出迷宫请你告诉小知最少需要走多少步每个格子不能重复走动。 迷宫中显示0的点是不可以走的。小知每次只能到达相邻的上下左右4个格子。 如何找到最短路径
我们可以按照这样的思路去找
从起点出发检查第1步可以到达的所有点判断是否为终点。依次从第1步到达的点出发 检查判断第2步可以到达的点是否为终点。依次从第2步到达的点出发检查判断第3步可以到达的点是否为终点。依次从第3步到达的点出发检查判断第4步可以到达的点是否为终点。依次从第4步到达的点出发检查判断第5步可以到达的点是否为终点。
6.找到终点程序结束步数为5。 问题建模
如何表示迷宫地图等信息呢
1.使用一个4*4的二维数组maze[][]来存储迷宫信息如果值位0表示不可走1表示可走。
2.使用一个4*4的二维数组used[][]来标记是否走过没走过为0走过的话为1。
例used[1][2]1表示maze[1][2]已经走过。 如何表示每次移动的过程 每次移动实际上就是坐标的变化。
上行标-1列标不变。
下行标1列标不变。
左行标不变列标-1。
右行标不变列标1。
我们可以用一个二维数组表示移动的方向。
例当前坐标为(1,2)向上移动就是
(1fx[0][0],2fx[0][1])得到(0,2)。 如何实现搜索的过程呢 1.我们需要使用队列(que)来实现,用一个结构体表示每次找到的点的坐标信息以及步数(x,y,cnt)。
2.将起点入队。
3.取出队首元素队首后移head将队首元素上下左右的四个点依次入队步数cnt要1同时判断是否到达终点若到达终点则终止程序。
4.重复步骤3直到找到终点或者队列为空即headtail 问题参考程序
#includebits/stdc.h
using namespace std;
struct wz{int x,y; //坐标int cnt; //步数
} que[1000],front,a; // front用来存每次取出的队首元素a存起点信息
int maze[5][5],used[5][5];
int fx[4][2]{{0,-1},{0,1},{-1,0},{1,0}};
int head1,tail1,sx1,sy1,ex3,ey4,flag0;//sx,sy,ex,ey分别表示开始结束的坐标
void bfs(wz a);
int main()
{for(int i1;i4;i)for(int j1;j4;j)cinmaze[i][j];a.xsx,a.ysy,a.cnt0;bfs(a);coutque[tail].cnt;return 0;
}
void bfs(wz a){que[head]a;//起点入队used[a.x][a.y]1;while(headtail){ //当队列非空时搜索frontque[head]; //取出队首head;//队首出队for(int i0;i4;i){ //检查队首元素四个方向的点int nxfront.xfx[i][0], nyfront.yfx[i][1];//下一次前进点的坐标if(nx1nx4ny1ny4!used[nx][ny]maze[nx][ny]){//点要在地图内且未被走过且非障碍tail; //队尾后移used[nx][ny]1; //标记用过que[tail].xnx; que[tail].yny;que[tail].cntfront.cnt1; //点入队步数1}if(nxexnyey){ //到达终点headtail1;//退出while循环break;//退出for循环}}}
}广度优先搜索模板
上面的走迷宫的过程就是一个广度优先搜索的过程从初始状态出发-1次转移(1步)能够到达的所有状态-2次转移(2步)能够到达的所有状态...n次转移能到达的所有状态。
我们常用广度优先搜索处理两种问题
1.最短路径问题。
2.是否有路线的问题。
void bfs(State a){队头指针 head1,队尾指针 tail1;起始状态a入队while(headtail){取出队首元素 Stateque[head];队头指针后移 head;尝试从队首元素出发可以得到的n个状态for(int i1;in;i){if(满足条件){队尾后移tail状态入队并标记}if(到达终点) {退出for和while循环。}}}
}训练森林救援
正在森林中探险的小知收到了一个求救信号。森林中有人受伤了小知需要尽快赶到伤者那里帮忙。森林可以看做是一个m*n的地图k表示小知p表示伤者森林中可以行走的地方用*表示其他符号表示不可走。
小知只能上下左右移动请你告诉小知他最少需要走多远。
【输入描述】第一行输入m和n分别表示地图的行和列
第二行输入地图的内容其中k表示小知的位置p表示伤者的位置*表示可以行走的地方其他符号均不可行走
【输出描述】如果小知能走到伤者的位置输出其最少距离
如果小知走不到伤者的位置输出No
【输入样例】
4 4
k * * *
* * *
* * * p
* * * *【输出样例】
5参考代码
#includebits/stdc.h
using namespace std;
struct wz{int x,y;int cnt;
} que[1000],front,a;
char maze[40][40];
int fx[4][2]{{0,-1},{0,1},{1,0},{-1,0}},used[40][40];
int head1,tail1,m,n,flag0;
void bfs(wz a);
int main()
{cinmn;for(int i1;im;i){for(int j1;jn;j){cinmaze[i][j];if(maze[i][j]k){a.xi; a.yj; a.cnt0;}}}bfs(a);if(flag)coutque[tail].cnt;elsecoutNo;return 0;
}
void bfs(wz a){que[head]a;while(headtail){frontque[head];head;for(int i0;i4;i) {int nxfront.xfx[i][0];int nyfront.yfx[i][1];if(!used[nx][ny](maze[nx][ny]*||maze[nx][ny]p)){tail;used[nx][ny]1;que[tail].xnx;que[tail].yny;que[tail].cntfront.cnt1;}if(maze[nx][ny]p){flag1;headtail1;break;}}}
}
从入门到算法再到数据结构查看全部文章请点击此处http://www.bigbigli.com/
