宽度优先搜索第n遍

宽度优先搜索第n遍

最近有种少年痴呆的感觉,停好几次车然后每次走的时候,发现自行车不见了,后来在同伴惊愕与无语的表情中想起,原来是停到别的地方去了,但是还好,这几次欠的饭钱准时还了,哈哈,今天把这道入门bfs小题研究的透透的,以后再忘,估计凑几眼,也能想起来。

***迷宫的最短路径
给定一个大小为N
M的迷宫。迷宫由通道和墙壁组成,每一步可以向相邻的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。如果不能到达,输出“不能走到那里”。(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账号...

(0)


相关推荐

  • 银河麒麟v10.1_银河麒麟v10系统

    银河麒麟v10.1_银河麒麟v10系统银河麒麟v10下载(服务器版桌面版)-2022-03-16更新银河麒麟桌面操作系统V10和银河麒麟高级服务器操作系统V10,分别推出了飞腾、鲲鹏、龙芯、申威、海光、兆芯六个版本银河麒麟高级服务器操作系统V10银河麒麟桌面操作系统V10…

    2022年10月16日
  • dsPIC33EP 时钟初始化程序

    dsPIC33EP 时钟初始化程序

  • 通达信资金净流入公式_通达信主力资金净流入指标

    V1:=(C*2+H+L)/4*10;V2:=EMA(V1,13)-EMA(V1,34);V3:=EMA(V2,5);V4:=2*(V2-V3)*5.5;庄家秘密撤:IF(V4<=0,V4,0),COLOR00FF00,LINETHICK2;庄家秘密进:IF(V4>=0,V4,0),COLORFF00FF,LINETHICK2;V5:=(HHV(INDEXH,8)-INDEXC)/…

  • python数组转化为字符串类型_python字符串类型

    python数组转化为字符串类型_python字符串类型python字符串数组转对象类型importjsoncontent=”'[{“_1″:”唐”,”_2″:12},{“_1″:”宋”,”_2″:2},{“_1″:”元”,”_2″:45}][{“_1″:”明”,”_2″:2},{“_1″:”清”,”_2″:4},{“_1″:”夏”,”_2″:5}][{“_1″:”商”,”_2″:11},{“_1″:”周”,”_2″:1},{“_1″:”晋”,”_2″:7}]”’#因为是字符串数组,一个字符串里含有三个数组,而每个数组里的对象都是以“,”隔开,

  • 语音信号处理习题

    语音信号处理习题二、问答题(每题5分,共20分)1、语音信号处理主要研究哪几方面的内容?语音信号处理是研究用数字信号处理技术对语言信号进行处理的一门学科,语音信号处理的理论和研究包括紧密结合的两个方面:一方面,从语言的产生和感知来对其进行研究,这一研究与语言、语言学、认知科学、心理、生理等学科密不可分;另一方面,是将语音作为一种信号来进行处理,包括传统的数字信号处理技术以及一些新的应用于语音信号的处理方法和技术。2、语音识别的研究目标和计算机自动语音识别的任务是什么?语音识别技术,也被称为自动语音

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号