迷宫算法广度优先

⑴ 广度优先搜索代码。也就是迷宫问题

这个bfs问题很容易掌握，是一种基础算法
首先记得添加<queue>队列容器
建立一个队列容器

之后 往里面压迷宫的起点 （通常是结构体）
之后在循环中加判断 判断当前取出的点是否能走，如果可以，压入它四周的四个点（视题目情况 不一定是四周） 再进行下一轮循环
循环体一般是while (!q.empty())
循环一开始一般是 p=q.front(); //取出第一个元素
q.pop(); //删除第一个元素

⑵ 深度优先和广度优先 的区别 ，用法。

1、主体区别

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件)。

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。

2、算法区别

深度优先搜索是每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。

广度优先搜索是每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。

3、用法

广度优先属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

深度优先即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。

(2)迷宫算法广度优先扩展阅读：

实际应用

BFS在求解最短路径或者最短步数上有很多的应用，应用最多的是在走迷宫上，单独写代码有点泛化，取来自九度1335闯迷宫一例说明，并给出C++/Java的具体实现。

在一个n*n的矩阵里走，从原点（0,0）开始走到终点（n-1,n-1），只能上下左右4个方向走，只能在给定的矩阵里走，求最短步数。n*n是01矩阵，0代表该格子没有障碍，为1表示有障碍物。

int mazeArr[maxn][maxn]; //表示的是01矩阵int stepArr = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4个方向，int visit[maxn][maxn]; //表示该点是否被访问过，防止回溯，回溯很耗时。核心代码。基本上所有的BFS问题都可以使用类似的代码来解决。

⑶ 迷宫算法复杂度如何计算

迷宫生成可以O(n*m)完成。走迷宫的话可以O(n*m*2)左右。
只要记录走到每一格的最优解就可以了。
最好不要用深度优先搜索。用广度优先的实现方便。

⑷ 算法设计：求广度优先搜索解决迷宫问题的思路

广度优先一般就是使用队列，创建一个队列，然后开始搜索起始点四周的结点加入队列，搜完一个结点后作出标记避免重复搜索，接着出队列继续搜索，知道搜索完队列内的结点。
广度优先就是先搜索四周的慢慢向四周扩展。

⑸ 广度优先搜索C语言算法

广度优先搜索算法，是按层遍历各个结点，以求出最短或最优的解，
常用于计算路径的最短距离，和最佳通路。
例如：迷宫的最短路径计算，推箱子的移动最小步数等小游戏，都是按广度搜索来进行的。

这个算法是教程中很经典的，有很多例子和代码。你可以好好研究！

如下是一段迷宫的最佳路径求解算法。
#include <stdio.h>

const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int maze[5][5],prev[5][5];
int que[32];
int qn;

void print(int x,int y)
{
if(prev[x][y]!=-2)
{
print(prev[x][y]>>3,prev[x][y]&7);
}
printf("(%d, %d)\n",x,y);
}

int main()
{
int i,j,cx,cy,nx,ny;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
scanf("%d",&maze[i][j]);
}
}
memset(prev,-1,sizeof(prev));
prev[0][0]=-2;
que[0]=0;
qn=1;
for(i=0;i<qn;i++)
{
cx=que[i]>>3;
cy=que[i]&7;
for(j=0;j<4;j++)
{
nx=cx+dx[j];
ny=cy+dy[j];
if((nx>=0)&&(nx<5)&&(ny>=0)&&(ny<5)&&(maze[nx][ny]==0)&&(prev[nx][ny]==-1))
{
prev[nx][ny]=(cx<<3)|cy;
que[qn++]=(nx<<3)|ny;
if((nx==4)&&(ny==4))
{
print(nx,ny);
return 0;
}
}
}
}
return 0;
}

⑹ 求广度优先算法C++走迷宫程序，可以显示路径

一般迷宫寻路可以用递归的算法，或者用先进后出的栈数据结构实现

用的是深度优先的算法，可以寻找到走出迷宫的路径

但本题要求求出最短的路径，这就要使用广度优先的算法

一般在程序中需要用到先进先出的队列数据结构

下面是程序的代码，主要原理是用到

quei，quej和prep三个数组来构成队列

分别储存路径的行，列坐标和上一个节点在队列中的位置

大致算法如下，右三个嵌套的循环实现

首先是第一个节点进入队列

当队列不空（循环1）

｛

遍历队列中每节点(循环2）

｛

将八个方向能够走的节点加入队列（循环3）

｝

旧的节点出列

｝

#include<iostream>
#include<ctime>
usingnamespacestd;

#defineMAXNUM50

voidmain()
{
intm,n,i,j,x;
cout<<"请输入迷宫大小"<<endl;
cin>>m>>n;
intmaze[MAXNUM][MAXNUM];

srand((int)time(NULL));
for(i=0;i<=m+1;i++){
for(j=0;j<=n+1;j++){
if(i==0||j==0||i==m+1||j==n+1)
maze[i][j]=1;
else
{
x=rand()%1000;
if(x>700){maze[i][j]=1;}//控制矩阵中1的个数，太多1迷宫很容易走不通
else{maze[i][j]=0;}
}
cout<<maze[i][j]<<'';
}
cout<<endl;
}

//以上是输入和迷宫生成，一下是走迷宫


intmove[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};
int*quei=newint[m*n];//储存行坐标队列
int*quej=newint[m*n];//储存列坐标队列
int*prep=newint[m*n];//储存之前一步在队列中的位置
inthead,rear,length;//队列头，队列尾，队列长度
head=0;rear=1;length=1;
quei[head]=1;quej[head]=1;prep[head]=-1;//入口位置进队列

intpos;//当前节点在队列中的位置，
intii,jj,ni,nj;//当前节点的坐标，新节点的坐标
intdir;//移动方向

if(maze[1][1]==1)length=0;//第一点就不能通过
elsemaze[1][1]=1;


while(length)//队列非空继续
{
for(pos=head;pos<head+length;pos++)//寻找这一层所有节点
{
ii=quei[pos];jj=quej[pos];//当前位置坐标
if(ii==m&&jj==n)break;
for(dir=0;dir<8;dir++)//寻找8个方向
{
ni=ii+move[dir][0];nj=jj+move[dir][1];//新坐标
if(maze[ni][nj]==0)//如果没有走过
{
quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新节点入队
rear=rear+1;
maze[ni][nj]=1;//标记已经走过
}
}
}
if(ii==m&&jj==n)break;
head=head+length;
length=rear-head;//这一层节点出列
}

if(ii==m&&jj==n)
{
while(pos!=-1)
{
cout<<'('<<quei[pos]<<','<<quej[pos]<<')';
pos=prep[pos];
if(pos!=-1)cout<<',';
}
}
else
{
cout<<"THEREISNOPATH."<<endl;
}

delete[]quei;
delete[]quej;
delete[]prep;
}

⑺ 迷宫算法 上下左右 优先级问题

迷宫一般采用递归算法，而且出口位置在算法开始时候是不知道的吧。而且迷宫的出口也不会固定到哪一个方向。如果采用枚举方法一般是按顺时针或者逆时针找，这样才可以用循环来做，如果采用优先，只能将每个方向定位，设一个常量，那样的话每次递归都要判断一下，非常麻烦，估计还比不用优先还慢一些。

⑻ 关于广度优先搜索算法

广度优先搜索算法，是按层遍历各个结点，以求出最短或最优的解，
常用于计算路径的最短距离，和最佳通路。
例如：迷宫的最短路径计算，推箱子的移动最小步数等小游戏，都是按广度搜索来进行的。

这个算法是教程中很经典的，有很多例子和代码。你可以好好研究！

如下是一段迷宫的最佳路径求解算法。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int maze[5][5],prev[5][5];
int que[32];
int qn;

void print(int x,int y)
{
if(prev[x][y]!=-2)
{
print(prev[x][y]>>3,prev[x][y]&7);
}
printf("(%d, %d)\n",x,y);
}

int main()
{
int i,j,cx,cy,nx,ny;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
scanf("%d",&maze[i][j]);
}
}
memset(prev,-1,sizeof(prev));
prev[0][0]=-2;
que[0]=0;
qn=1;
for(i=0;i<qn;i++)
{
cx=que[i]>>3;
cy=que[i]&7;
for(j=0;j<4;j++)
{
nx=cx+dx[j];
ny=cy+dy[j];
if((nx>=0)&&(nx<5)&&(ny>=0)&&(ny<5)&&(maze[nx][ny]==0)&&(prev[nx][ny]==-1))
{
prev[nx][ny]=(cx<<3)|cy;
que[qn++]=(nx<<3)|ny;
if((nx==4)&&(ny==4))
{
print(nx,ny);
return 0;
}
}
}
}
return 0;
}

⑼ C语言用图的广度优先遍历做漫步迷宫问题

这是我们老师给我们上数据结构课的课件

#include "stdio.h"
typedef int datatype; /*假定线性表元素的类型为整型*/
#define maxsize 1024 /*假定线性表的最大长度为1024*/
# define n 100 /* 图的顶点最大个数 */
typedef char VEXTYPE; /* 顶点的数据类型 */
typedef float ADJTYPE; /* 权值类型 */
typedef struct
{ VEXTYPE vexs[n] ; /* 顶点信息数组 */
ADJTYPE arcs[n][n] ; /* 边权数组 */
int num ; /* 顶点的实际个数 */
}GRAPH;

/***********************1。置空图**********************/
void GraphInit(GRAPH *L)
{
L->num=0;
}

/***********************2。求结点数**********************/
int GraphVexs(GRAPH *L)
{
return(L->num);
}

/***********************3。创建图**********************/
void GraphCreate(GRAPH *L)
{
int i,j;
GraphInit(L);
printf("请输入顶点数目：");
scanf("%d",&L->num);
printf("请输入各顶点的信息(单个符号）：");
for(i=0;i<L->num;i++)
{
fflush(stdin);
scanf("%c",&L->vexs[i]);
}
printf("请输入边权矩阵的信息：");
for(i=0;i<L->num;i++)
{
for(j=0;j<L->num;j++)
{
scanf("%f",&L->arcs[i][j]);
}
}
printf("图已经创建完毕！");
}

/***********************4。图的输出**********************/
void GraphOut(GRAPH L)
{
int i,j;
printf("\n图的顶点数目为：%d",L.num);
printf("\n图的各顶点的信息为：\n");
for(i=0;i<L.num;i++)
printf("%c ",L.vexs[i]);
printf("\n图的边权矩阵的信息为：\n");
for(i=0;i<L.num;i++)
{
for(j=0;j<L.num;j++)
{
printf("%6.2f ",L.arcs[i][j]);
}
printf("\n");
}
printf("图已经输出完毕！");
}

/***********************5。图的深度周游**********************/
void DFS(GRAPH g,int qidian,int mark[])
//从第qidian个点出发深度优先周游图g中能访问的各个顶点
{
int v1;
mark[qidian]=1;
printf("%c ",g.vexs[qidian]);
for(v1=0;v1<g.num;v1++)
{
if(g.arcs[qidian][v1]!=0&&mark[v1]==0)
DFS(g,v1,mark);
}
}
/***********************6。图的深度周游**********************/
void GraphDFS(GRAPH g)
//深度优先周游图g中能访问的各个顶点
{
int qidian,v,v1,mark[maxsize];
printf("\n深度周游：");
printf("\n请输入起点的下标：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
//printf("v=%d ",v);
v1=v%g.num;
if(mark[v1]==0)
DFS(g,v1,mark);
}
}
typedef int DATATYPE; //队列元素的数据类型
typedef struct
{
DATATYPE data[maxsize]; //队中元素
int front,rear; //队头元素下标、队尾元素后面位置的下标
} SEQQUEUE;
/*****************************************************************************/
void QueueInit(SEQQUEUE *sq)
//将顺序循环队列sq置空（初始化）
{
sq->front=0;
sq->rear=0;
}
/*****************************************************************************/
int QueueIsEmpty(SEQQUEUE sq)
//如果顺序循环队列sq为空，成功返回1，否则返回0
{
if (sq.rear==sq.front)
return(1);
else
return(0);
}
/*****************************************************************************/
int QueueFront(SEQQUEUE sq,DATATYPE *e)
//将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0
{
if (QueueIsEmpty(sq))

else

}
/*****************************************************************************/
int QueueIn (SEQQUEUE *sq,DATATYPE x)
//将元素x入队列sq的队尾，成功返回1，失败返回0
{
if (sq->front==(sq->rear+1)%maxsize)
{
printf("queue is full!\n");
return 0;
}
else
{
sq->data[sq->rear]=x;
sq->rear=(sq->rear+1)%maxsize;
return(1);
}
}
/*****************************************************************************/
int QueueOut(SEQQUEUE *sq)
//将队列sq队首元素出队列，成功返回1,失败返回0
{
if (QueueIsEmpty(*sq))
{
printf("queue is empty!\n");
return 0;
}
else
{
sq->front=(sq->front+1)%maxsize;
return 1;
}
}
/***********************7。图的广度周游**********************/
void BFS(GRAPH g,int v,int mark[])
//从v出发广度优先周游图g中能访问的各个顶点
{
int v1,v2;
SEQQUEUE q;
QueueInit(&q);
QueueIn(&q,v);
mark[v]=1;
printf("%c ",g.vexs[v]);
while(QueueIsEmpty(q)==0)
{
QueueFront(q,&v1);
QueueOut(&q);
for(v2=0;v2<g.num;v2++)
{
if(g.arcs[v1][v2]!=0&&mark[v2]==0)
{
QueueIn(&q,v2);
mark[v2]=1;
printf("%c ",g.vexs[v2]);
}
}
}
}
/***********************8。图的广度周游**********************/
void GraphBFS(GRAPH g)
//深度优先周游图g中能访问的各个顶点
{
int qidian,v,v1,mark[maxsize];
printf("\n广度周游：");
printf("\n请输入起点的下标：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
BFS(g,v1,mark);
}
}

/***********************主函数**********************/

void main()
{
GRAPH tu;
GraphCreate(&tu);
GraphOut(tu);
GraphDFS(tu);
GraphBFS(tu);
}

⑽ 一般迷宫游戏用到什么算法

状压DP，或者记忆化搜索。
一般的就是F[i,j,k]表示站在i,j点，当前已经得到了k的状态。然后转移。