广度搜索

标签: 笔记  队列  算法  数据结构  c语言

广度搜索的基本使用方法

广度搜索不同于深度搜索,是一种一步一步进行的过程,每一个点只记录一遍。需要用到队列记录每一步可以走到的位置,找到目标位置输出步数即可。
用到的知识:结构体、队列
如图
本图选自《啊哈!算法》
首先我们需要定义一个结构体来存储每个遍历到的点和步数

struct node{
	int x;
	int y;
	int s;
};

广搜不会用到递归,所以可以直接在主函数里写,这里需要定义一个结构体队列

	struct node que[2501]; //我们设置边界为50,所以队列大小取50平方即可
	int a[51][51]={0}; //我们设置1为墙,0为路径,int类型即可,当然,字符类型也可
	int b[51][51]={0};  //b数组用来记录走过的点
	int i,j,tx,ty,k,n,m,p,q,head,tail,startx,starty,flag=0;
	int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; //列举四个方向
	scanf("%d %d",&n,&m);  // 取行和列
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	scanf("%d %d %d %d",&startx,&starty,&p,&q);

初始化队列并将起始点入列

	head=1;
	tail=1;
	que[tail].x=startx;
	que[tail].y=starty;
	que[tail].s=0;
	tail++;
	b[startx][starty]=1;

遍历

	while(head<tail)  //当队列不为空时
	{
		for(k=0;k<=3;k++) //按照顺时针方向,右下左上遍历头的下一个点
		{
			tx=que[head].x+next[k][0];
			ty=que[head].y+next[k][1];
			if(tx<1 || tx>n || ty<1 || ty>m)  //判断是否越界
				continue;
			if(a[tx][ty]==0 && b[tx][ty]==0) //判断是否可行及是否走过
			{          // 将点入列
				b[tx][ty]=1;
				que[tail].x=tx;
				que[tail].y=ty;
				que[tail].s=que[head].s+1;  //下一个点需要的步数是上一个点的步数+1
				tail++;
			}
			//判断是否找到目标点
			if(tx==p && ty==q)
			{
				flag=1;  //这两句不可颠倒
				break;
			}
		}
		if(flag==1)
			break;
		head++;  //很重要,头+1,遍历下一个
	}
	if(flag==1)  //如果可以找到目标点,输出最少步数
		printf("Escaped at least %d minute(s)\n",que[tail-1].s);
 	else         //否则被困住
 		printf("Trapped!\n");

完整代码

#include<stdio.h>

struct node{
	int x;
	int y;
	int z;
	int s;
};

int main()
{
	struct node que[2701];
	char a[32][32][32];
	int b[32][32][32]={0};
	int next[6][3]={{0,0,1},{0,1,0},{1,0,0},{0,0,-1},{0,-1,0},{-1,0,0}};
 	int n,m,c,i,j,k,startx,starty,startz,head,tail,tx,ty,tz,p,q,d,flag=0;
 	scanf("%d %d %d",&n,&m,&c);
 	for(i=0;i<n;i++)
 		for(j=0;j<m;j++)
 		{
 			scanf("%s",a[i][j]);
 			for(k=0;k<c;k++)
 			{
 				if(a[i][j][k]=='S')
 				{
 					startx=i;
 					starty=j;
 					startz=k;
				}
				if(a[i][j][k]=='E')
				{
					p=i;
					q=j;
					d=k;
				}
			}
		}
	head=1;
	tail=1;
	b[startx][starty][startz]=1;
	que[tail].x=startx;
	que[tail].y=starty;
	que[tail].z=startz;
	que[tail].s=0;
	tail++;
	while(head<tail)
	{
		for(k=0;k<=5;k++)
		{
			tx=que[head].x+next[k][0];
			ty=que[head].y+next[k][1];
			tz=que[head].z+next[k][2];
			if(tx<0 || tx>n-1 || ty<0 || ty>m-1 || tz<0 || tz>c)
				continue;
			if(a[tx][ty][tz]!='#' && b[tx][ty][tz]==0)
			{
				b[tx][ty][tz]=1;
				que[tail].x=tx;
				que[tail].y=ty;
				que[tail].z=tz;
				que[tail].s=que[head].s+1;
				tail++;
			}
			if(tx==p && ty==q && tz==d)
			{
				flag=1;
				break;
			}
		}
		if(flag==1)
			break;
		head++;
	}
	if(flag==1)
		printf("Escaped at least %d minute(s)\n",que[tail-1].s);
 	else
 		printf("Trapped!\n");
 	
 	return 0;
}```
以上
版权声明:本文为weixin_45934372原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45934372/article/details/104312344

智能推荐

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

猜你喜欢

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...

力扣困难难度 第4题 寻找两个正序数组的中位数

先看一眼题 我的思路: 设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。 ·每次比较nums[i]nums[j],如果前者小则i++,否则j++ ·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以...

[国家集训队]小Z的袜子(莫队)

[国家集训队]小Z的袜子 题目描述 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命…… 具体来说,小Z把这NN只袜子从1到NN编号,然后从编号LL到RR(LL 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同...