前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C语言问题-数据结构-迷宫问题

C语言问题-数据结构-迷宫问题

作者头像
杨鹏伟
发布2021-01-27 09:54:03
1.8K0
发布2021-01-27 09:54:03
举报
文章被收录于专栏:ypw

小叙:好长时间没写代码,确实有点生疏了。准备考研中,复习数据结构就想着我可以借此练练代码,刷一个数据结构专题。 题目·链接 题意:很直白一个BFS问题。

思路:具体见代码

我们首先要理解宽搜的精髓。 然后就是用一个队列,存下坐标以及当前路径长度。 形象的来说就是像水波纹一样的扩散,中心就是起点,然后波纹不断扩大,途中遇见终点我们就停下来。 那么对于同一圆环(题中相当于四个方向),半径一样(路径长度一样)。

具体还是得自己多体会啊! 打卡,高数,英语,数据结构复习第一天。

代码语言:javascript
复制
#include<bits/stdc++.h>
#define maxn 203 
using namespace std;

struct node{
	int x;
	int y;
	int len;//纪录当前路的长度。 
};

int startx,starty,endx,endy;//记录起点跟终点 
char mapp[maxn][maxn];//记录地图 
bool vis[maxn][maxn];//纪录是否访问过了。
int f[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};//定义方向数组
int n,m; 

int ans;

int BFS(int startx,int starty){
	queue<node> qu;
	while(!qu.empty()) qu.pop();
	
	node st = {startx,starty,0};
	qu.push(st);//把第一个起始点加入 
	vis[startx][starty] = 1;//标记这个点已经访问过了
	
	while(!qu.empty()){//如果对头非空,说明
		node res = qu.front();
		int xx = res.x;
		int yy = res.y;
		int l = res.len; 
		for(int k=0;k<4;k++){
			int fx = xx + f[k][0];
			int fy = yy + f[k][1];
			
			if(vis[fx][fy] == 1 || mapp[fx][fy]=='#' || fx<1 || fy<1 || fx>n || fy>m) continue;
			res = {fx,fy,l + 1};
			vis[fx][fy] = 1;//标记访问过了 
			qu.push(res);//加入队列 
			
			
			if(fx == endx && fy == endy) return res.len;
			
		}
		qu.pop();//找完以后将当前队头元素出队 
	} 
	return -1;//没有找到这样的一条路径。 
} 



int main(){
	int t;
	cin>>t;
    while(t--){
    	cin>>n>>m;
    	for(int i=0;i<=n+1;i++){//先对地图进行初始化 
    		for(int j=0;j<=m+1;j++){
    			mapp[i][j] = '#';
			}
		}
    	memset(vis,0,sizeof(vis));
    	
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>mapp[i][j];
    			if(mapp[i][j]=='S'){
    				startx = i;
					starty = j; 
				}
				if(mapp[i][j]=='E'){
					endx = i;
					endy = j;
				}
			}
		}
		ans = BFS(startx,starty);
		cout<<ans<<endl;
	}
	return 0;
} 
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/01/21 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档