宽度优先搜索第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)


相关推荐

  • UART接口定义_uart接口图片

    UART接口定义_uart接口图片认识UART接口嵌入式里面说的串口,一般是指UART口,但是我们经常搞不清楚它和COM口的区别,以及RS232,TTL等关系,实际上UART,COM指的物理接口形式(硬件),而TTL、RS-232是指的电平标准(电信号)。UART有4个pin(VCC,GND,RX,TX),用的TTL电平,低电平为0(0V),高电平为1(3.3V或以上)。COM口是我们台式机上面常用的口(下图)…

  • windows关闭135,139端口_危险端口有哪些

    windows关闭135,139端口_危险端口有哪些我用nmap扫描自己的主机,发现自己的某些端口开启着的,我去了解了一下139端口这个端口比较危险139端口是NetBIOSSession端口,用来文件和打印共享如果你是单机,不是企业内部网里的成员,为了保护计算机的安全关闭这个端口比较好。下面是步骤1开始键输入控制面板点击进入控制面板然后点击进入网络和internet2点击进入网络和共享中心点击进入更改适配器设置在…

    2022年10月17日
  • 分析:电信业再重组是更竞争还是更垄断

    分析:电信业再重组是更竞争还是更垄断

  • 出现Permission denied的解决办法(750权限谨慎使用)

    出现Permission denied的解决办法(750权限谨慎使用)提示Permissiondenied解决的办法:$sudochmod-R777某一目录其中-R是指级联应用到目录里的所有子目录和文件777是所有用户都拥有最高权限

  • 单隐层前馈神经网络网络构造_前馈型神经网络常用于

    单隐层前馈神经网络网络构造_前馈型神经网络常用于这篇博客主要介绍神经网络基础,单隐层前馈神经网络与反向传播算法。神经网络故名思议是由人的神经系统启发而得来的一种模型。神经网络可以用来做分类和回归等任务,其具有很好的非线性拟合能力。接下来我们就来详细介绍一下但隐层前馈神经网络。首先我们来看一下神经元的数学模型,如下图所示:可以看到为输入信号,而神经元最终输出为,由此我们可以看到,单个神经元是多输入单输出的。但是从上图我们可以看到,…

    2022年10月30日
  • linux ext4无法使用超过16T磁盘的解决办法

    linux ext4无法使用超过16T磁盘的解决办法

发表回复

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

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