迷宫问题
定义一个二维数组：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0 Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4) C++版本一
BFS+路径保存
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
int dx[4]={1,0,0,-1};//四个方向
int dy[4]={0,1,-1,0};
int f=0,r=1;
int map[5][5];
struct line
{
int x,y,t;
}road[1000],temp;
bool judge(line a)//判断是否出界或是走过
{
return a.x >=0&&a.x <5&&a.y >=0&&a.y <5&&!map[a.x ][a.y ];
}
void PRINTF(int i)//递归输出路径
{
if(road[i].t!=-1)
{
PRINTF(road[i].t );
printf("(%d, %d)\n",road[i].x,road[i].y );
}
}
void bfs()
{
road[f].x =0;
road[f].y =0;
road[f].t =-1;
while(f<r)//控制并记录路径
{
for(int i=0;i<4;i++)
{
temp.x =road[f].x +dx[i];
temp.y =road[f].y +dy[i];
if(!judge(temp))
continue;
else
{
map[temp.x ][temp.y ]=1;
road[r].x =temp.x ;
road[r].y=temp.y;
road[r].t= f;
r++;
}
if(temp.x ==4&&temp.y ==4)
PRINTF(f);
}f++;
}
}
int main()
{
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
scanf("%d",&map[i][j]);
printf("(0, 0)\n");
bfs();
printf("(4, 4)\n");
return 0;
}
C++版本二
迷宫问题困扰了我很久很久，最后还是靠别人的帮忙，明白了思路，才最终写了出来。这个迷宫问题不是难在BFS寻找最短步数中，而是难在怎么去记录他的正确走法的坐标，我尝试了好几种方法都无效。
最后，我明白了正确的方法，要多开一个5*5的数组，来记录每一个坐标上一步是什么。这里可以记录上一步到这里的方向向量，也可以直接记录上一步的坐标。当BFS寻找到右下角的点的时候，从最后一个点开始向上通过这个数组往回推，得到一系列坐标，可以存放在栈中，也可以直接放在一个数组中，最后输出这些坐标就可以了。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=6;
bool vst[maxn][maxn]; // 访问标记
int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 方向向量 右，左，上，下
int migong[maxn][maxn];
int fang[maxn][maxn];//记录上一步的方向向量
struct State // BFS 队列中的状态数据结构
{
int x,y; // 坐标位置
int Step_Counter; // 搜索步数统计器
};
State t,a[30];
bool CheckState(State s) // 约束条件检验
{
if(!vst[s.x][s.y] && s.x>=0 && s.x<5 && s.y>=0 && s.y<5) // 满足条件
return 1;
else // 约束条件冲突
return 0;
}
void bfs(State st)
{
queue <State> q; // BFS 队列
State now,next; // 定义2 个状态，当前和下一个
st.Step_Counter=0; // 计数器清零
q.push(st); // 入队
vst[st.x][st.y]=1; // 访问标记
int k=0,i,j;
while(!q.empty())
{
now=q.front(); // 取队首元素进行扩展
if(now.x==4 && now.y==4) // 出现目标态，此时为Step_Counter 的最小值，可以退出即可
{
printf("%d\n",now.Step_Counter); // 做相关处理
a[k++]=now;
next=now;
while(1)
{
switch(fang[now.x][now.y])
{
case 0:
next.y=now.y-1;
break;
case 1:
next.y=now.y+1;
break;
case 2:
next.x=now.x-1;
break;
case 3:
next.x=now.x+1;
}
a[k++]=next;
now=next;
if(next.x==0&&next.y==0)
break;
}
k--;
while(k>=0)
{
printf("(%d, %d)\n",a[k].x,a[k].y);
k--;
}
return;
}
for(int i=0;i<4;i++)
{
next.x=now.x+dir[i][0]; // 按照规则生成 下一个状态
next.y=now.y+dir[i][1];
next.Step_Counter=now.Step_Counter+1; // 计数器加1
if(CheckState(next)) // 如果状态满足约束条件则入队
{
fang[next.x][next.y]=i;
q.push(next);
vst[next.x][next.y]=1; //访问标记
}
}
q.pop(); // 队首元素出队
}
return;
}
int main()
{
int i,j;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
{
scanf("%d",&migong[i][j]);
if(migong[i][j]==1)
{
vst[i][j]=true;
}
}
t.x=0;
t.y=0;
bfs(t);
return 0;
}
C++版本三
BFS
#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
struct obj
{
int xx,yy,index;//index记录(xx,yy)这个点在a[]和pre[]中的下标
};
int n,m;
int map[102][102];
queue<struct obj> q;
struct obj S,T;
struct obj a[102*102+3];
int pre[102*102+3];//pre[i]记录a[i]这个点在广搜中的前驱结点
int index;//a[]和pre[]的下标
int dx[4]={-1,0,1,0};//上右下左
int dy[4]={0,1,0,-1};
void BFS();
int main(int argc, char *argv[])
{
struct obj tt[102*102+3];//用于正向输出路径
freopen("7084.in","r",stdin);
int i,j;
n=m=5;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%d",&map[i][j]);
}
}
S.xx=0; S.yy=0; S.index=0;//出发点在广搜过程中，放在a[]第0号位置
T.xx=n-1; T.yy=m-1; T.index=-1;
index=0;
a[index]=S;
pre[index]=-1;//广搜过程中，出发点没有前驱结点
index++;
BFS();
if(T.index==-1) printf("no way!\n");
else
{
//逆向输出路径
/*for(i=index-1;pre[i]>=0;)
{
printf("(%d,%d)\n",a[i].xx,a[i].yy);
i=pre[i];
}
printf("(%d,%d)\n",S.xx,S.yy);
*/
//正向输出路径
j=0;
for(i=index-1;pre[i]>=0;)
{
tt[j]=a[i];
j++;
i=pre[i];
}
printf("(%d, %d)\n",S.xx,S.yy);
for(j=j-1;j>=0;j--)
{
printf("(%d, %d)\n",tt[j].xx,tt[j].yy);
}
}
return 0;
}
void BFS()
{
int i,txx,tyy;
struct obj temp;
q.push(S);
while(!q.empty())
{
for(i=0;i<4;i++)
{
txx=q.front().xx+dx[i];
tyy=q.front().yy+dy[i];
if(txx>=0&&txx<n&&tyy>=0&&tyy<m&&map[txx][tyy]==0)
{
temp.xx=txx;
temp.yy=tyy;
temp.index=index;
q.push(temp);
map[txx][tyy]=1;
a[index]=temp;
pre[index]=q.front().index;
index++;
if(temp.xx==T.xx&&temp.yy==T.yy)
{
T.index=temp.index;
return ;
}
}
}
q.pop();
}
} C++版本四（有问题,已解决）
BFS
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
int n;
int MAP[10][10];
int vis[10][10];
int dir1[4]={-1,1,0,0};
int dir2[4]={0,0,1,-1};
struct node{
//int x,y;
int step;
int bx[30];
int by[30];
}front1,start,temp;
void bfs(){
queue <node>Q;
while(!Q.empty())
Q.pop();
start.bx[0]=0;
start.by[0]=0;
start.step=0;
//memset(start.bu,0,sizeof(start.bu));
memset(vis,0,sizeof(vis));
vis[start.bx[0]][start.by[0]]=1;
Q.push(start);
int x,y;
while(!Q.empty()){
front1=Q.front();
Q.pop();
for(int i=0;i<4;i++){
x=front1.bx[front1.step]+dir1[i];
y=front1.by[front1.step]+dir2[i];
if(x>=0&&x<=4&&y>=0&&y<=4&&MAP[x][y]!=1&&vis[x][y]==0){
vis[x][y]=1;
temp.step=front1.step+1;
int s=temp.step;
temp.bx[s]=x;
temp.by[s]=y;
if(x==4&&y==4) {
for(int j=0;j<=temp.step;j++)
printf("(%d,%d)\n",temp.bx[j],temp.by[j]);
return;
}
Q.push(temp);
//printf("%d\n",temp.step);
}
}
}
}
int main()
{ for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
scanf("%d",&MAP[i][j]);
}
}
bfs();
//cout << "Hello world!" << endl;
return 0;
}
输入实例
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0 输出实例
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4) 是不是觉得很正常
让我们把出口改为（0,4）
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(0,4)
看最后？？？？
啥东西
一直不懂
终于问过大佬后
发现因为结构里面有数组所以要拷贝前一个整个结构
temp=front1;
下面是改过的C++版本四
BFS
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
int n;
int MAP[10][10];
int vis[10][10];
int dir1[4]={-1,1,0,0};
int dir2[4]={0,0,1,-1};
struct node{
//int x,y;
int step;
int bx[30];
int by[30];
}front1,start,temp;
void bfs(){
queue <node>Q;
while(!Q.empty())
Q.pop();
start.bx[0]=0;
start.by[0]=0;
start.step=0;
//memset(start.bu,0,sizeof(start.bu));
memset(vis,0,sizeof(vis));
vis[start.bx[0]][start.by[0]]=1;
Q.push(start);
int x,y;
while(!Q.empty()){
front1=Q.front();
Q.pop();
for(int i=0;i<4;i++){
x=front1.bx[front1.step]+dir1[i];
y=front1.by[front1.step]+dir2[i];
temp=front1;
if(x>=0&&x<=4&&y>=0&&y<=4&&MAP[x][y]!=1&&vis[x][y]==0){
vis[x][y]=1;
temp.step=front1.step+1;
int s=temp.step;
temp.bx[s]=x;
temp.by[s]=y;
if(x==4&&y==4) {
for(int j=0;j<=temp.step;j++)
printf("(%d, %d)\n",temp.bx[j],temp.by[j]);
return;
}
Q.push(temp);
//printf("%d\n",temp.step);
}
}
}
}
int main()
{ for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
scanf("%d",&MAP[i][j]);
}
}
bfs();
//cout << "Hello world!" << endl;
return 0;
}
华为成长空间 480人发布
