广度优先搜索算法实现逃离迷宫

今天给大家带来的是用广度优先算法实现逃离迷宫

上代码

//广度优先搜索算法 
#include 
struct	note //为后续队列的操作定义结构体 
{int x;int y;int s;
} que[2501];
int main()
{//struct note que[2501]; int a[51][51] = {0} , book[51][51] = {0}; //初始化迷宫数组和标记数组 int next[4][2] = { { 0 , 1 }, //方向数组 { 1 , 0 },{ 0 , -1 },{ -1 , 0 } };int head , tail; //定义队列指针 int i , j , k , n , m , startx , starty , p , q , tx , ty , flag;scanf("%d %d" , &n , &m ); //输入迷宫大小 for ( i = 1 ; i <= n ; i++ )for ( j = 1 ; j <= m ; j++ )scanf("%d" , &a[i][j]); //输入迷宫地形 scanf("%d %d %d %d" , &startx , &starty , &p , &q); //输入入口和出口 head = 1;tail = 1;//指针初始化 que[tail].x = startx;que[tail].y = starty;que[tail].s = 0;//存储初始坐标和初始化步数 tail++;//tail指针指向后面一个空位 book[startx][starty] = 1;//标记入口 flag = 0;//flag为0就是没找到终点，为1则找到 while ( head < tail ) //当队列不为空时循环（其实会一直循环，后面会break出来） {for ( k = 0 ; k <= 3 ; k++ ){tx = que[head].x + next[k][0];ty = que[head].y + next[k][1];//尝试方向，顺序为右-下-左-上 if ( tx < 1 || tx > n || ty < 1 || ty > m ) //判断是否越界，如越界则改变寻找方向 continue;if ( a[tx][ty] == 0 && book[tx][ty] == 0 ) //判断下一步是否有障碍物或是否被走过 {book[tx][ty] = 1; //标记被走过 que[tail].x = tx;que[tail].y = ty;//尝试下一步 que[tail].s = que[head].s + 1; //步数为父亲的步数加1 printf("head = %d  que[head] = %d,%d  step = %d\n" ,head , que[head].x , que[head].y , que[head].s ); //测试 tail++; //tail指针指向下一个空位 printf("tail = %d  que[tail] = %d,%d  step = %d\n" ,tail , que[tail].x , que[tail].y , que[tail].s ); //测试 }if  ( tx == p && ty == q ) //如到达位置则退出循环 {flag = 1;break;}}if ( flag == 1 ) //如已找到则退出循环 break;head++; //head指针往后扩展 }printf("%d" , que[tail - 1].s); //注意这里要tail-1，因为tail指针是指向后面一个空位的 return 0;
}

这个问题还有用深度优先算法实现的，感兴趣可以点进去看一下

深度优先解法

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！