最近有种少年痴呆的感觉,停好几次车然后每次走的时候,发现自行车不见了,后来在同伴惊愕与无语的表情中想起,原来是停到别的地方去了,但是还好,这几次欠的饭钱准时还了,哈哈,今天把这道入门bfs小题研究的透透的,以后再忘,估计凑几眼,也能想起来。
***迷宫的最短路径
给定一个大小为NM的迷宫。迷宫由通道和墙壁组成,每一步可以向相邻的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。如果不能到达,输出“不能走到那里”。(N,M<=50,起点,终点分别用S,G表示)
输入样例:N=5,M=5
#S###
…##.
#.###
…###
…G##
输出:5****
//简单BFS,//最短路问题
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
char maze[50][50];
bool vis[10][10];
int n,m;
int sx,sy;
int ex,ey;
int dir[4][2]={0,1,1,0,-1,0,0,-1} ;
struct node
{
int x,y,step;
};
void bfs()
{
node p;//第一个结构体
p.x=sx;
p.y=sy;//起点坐标
p.step=0;
queue<node>q;
q.push(p);//进队列
vis[sx][sy]=1;//标记
while(!q.empty())//判断是否为空
{//第二个结构体
node tmp=q.front();//新结构体讲队列第一个元素赋值
q.pop();//出队列
if(tmp.x==ex&&tmp.y==ey)//如果第一个出队列的元素坐标与终点坐标相等的话。
{cout<<"最短路为"<<tmp.step<<endl;
return;
}
for(int i=0;i<4;i++)
{int xx=tmp.x+dir[i][0];
int yy=tmp.y+dir[i][1];
if(maze[xx][yy]!='#'&&xx>0&&yy>0&&xx<=n&&yy<=m&&!vis[xx][yy])//和dfs一样判断条件
{
node tp;//第三个结构体
tp.x=xx;//存储移动后的坐标
tp.y=yy;
tp.step=tmp.step+1;//计步
vis[xx][yy]=1;//标记
q.push(tp);//入队列
}
}
}
cout << "不能走到那里!" << endl;
}
int main()
{
while(~scanf("%d%d",&n,&m)&&n!=0&&m!=0)
{ memset(vis,0,sizeof(vis));//给标记数组清零
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{cin>>maze[i][j];
if(maze[i][j]=='S')
{sx=i;//起点坐标
sy=j;
}//更新一波
if(maze[i][j]=='G')
{ex=i;//终点坐标
ey=j;}
}
bfs();
}
}
昨天下午又大了一遍输出怎么搞都是0;今天早上醒来,神清气爽,一下子就发现了一个逻辑错误
node top;//这个结构题不能定义在判断语句里面,否则会出现错误
top.x=xx;
top.y=yy;
top.ans=tp.ans+1;
vis[top.x][top.y]=1;
q.push(top);
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<time.h>
#include<queue>
#include<stack>
using namespace std;
int n,m;
int dir[4][2]={0,1,1,0,-1,0,0,-1};
char map[10][10];
int vis[10][10];
int sx,sy,ex,ey;
struct node{
int x;
int y;
int ans;
};
node top;
void bfs()
{
//稳住第一个结构体
node p;
p.x=sx;
p.y=sy;
p.ans=0;
queue<node> q;
q.push(p);
vis[p.x][p.y]=1;
while(!q.empty())
{
//第二个结构体
node tp=q.front();
q.pop();
if(tp.x==ex&&tp.y==ey)
{
cout<<"输出"<<top.ans<<endl;
return ;
}
for(int i=0;i<4;i++)
{
int xx=tp.x+dir[i][0];
int yy=tp.y+dir[i][1];
if(xx>=0&&xx<n&&yy>=0&&yy<m&&map[xx][yy]!='#'&&!vis[xx][yy])
{
node top;//删去这句即可
top.x=xx;
top.y=yy;
top.ans=tp.ans+1;
vis[top.x][top.y]=1;
q.push(top);
}
}
}
cout << "不能走到那里!" << endl;
}
int main()
{
memset(vis,0,sizeof(vis));
while(cin>>n>>m)
{
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>map[i][j];
if(map[i][j]=='S')
{
sx=i;
sy=j;
}
if(map[i][j]=='G')
{
ex=i;
ey=j;
}
}
bfs();
} return 0;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114895.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...