斯内克

用户名：Siuving

访问量：16523

签　名：

冰冻三尺非一日之寒

等　　级
排　　名	924
经　　验	3471
参赛次数	0
文章发表	31
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

发工资咯（贪心法）
浏览：1080

公交汽车（可同等于完全背包问题）
浏览：408

蓝桥杯算法训练VIP-拦截导弹（O(n*log n)量级）
浏览：608

你可能喜欢

C语言程序设计教程（第三版）课后习题11.3 （C++代码）

迷宫问题（广度优先搜索，巧妙解决越界问题，解析详细易懂）

　　作者: 斯内克　　　　发表时间：2019-10-11 17:00:27 浏览：1092　|　评论：0　

原题链接：迷宫问题

```
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct DirectInc{
	int dx,dy;
};
struct DataType{
	int x,y,tot;
};
DirectInc mov[4]={{0,1},{1,0},{0,-1},{-1,0}};//走的方式，即x,y坐标的更新

const int MAXN=105;//在堆中建立一个大的迷宫格子 ，防止越界问题 
char f[MAXN][MAXN];

int ShortPathQue(DirectInc Sta,DirectInc End){
	
	queue<DataType> Que;
	int i,j,g,h,v;
	
	DataType dat={Sta.dx,Sta.dy,0};//初始步数为 0 
	Que.push(dat);//入口点进队列
	f[Sta.dx][Sta.dy]='#';
	
	while(!Que.empty()){//如果队列为空，说明找不到终点，即所有连通的格子都遍历完了，仍未到达终点 
		dat=Que.front();//取队头元素，即当前定位格子，随时在更新 
		g=dat.x;h=dat.y;
		
		for(v=0;v<4;v++){//4个方向 
			i=g+mov[v].dx;j=h+mov[v].dy;
			
			if(f[i][j]=='-'||f[i][j]=='E'){//通路，将该点入队列 
					
				DataType data={i,j,dat.tot+1};//步数要更新，在上一步的基础上+1 
				Que.push(data);f[i][j]='#';//搜索过的格子，要去除，避免反复在循环 
				
				if(i==End.dx&&j==End.dy)//找到终点
					return data.tot;
			}
		}Que.pop();//很重要，将队头元素出队，即我们用探寻过的格子作为新的起点 
	}
	return -1; //未找到终点 
} 
int main(){
	int T,N,M;
	cin>>T;
	while(T--){
		memset(f,'#',sizeof f);//迷宫初始化，巧妙解决边界问题，每完成一组，就要进行初始化 
		DirectInc Sta,End;
		cin>>N>>M;
		for(int i=1;i<=N;i++)
			for(int j=1;j<=M;j++){
				cin>>f[i][j];
				if(f[i][j]=='S') {Sta.dx=i,Sta.dy=j;}
				if(f[i][j]=='E') {End.dx=i,End.dy=j;}//记录下起点和终点 
				}
		int length;
		length=ShortPathQue(Sta,End);
		cout<<length<<endl;
	}
	return 0;
} 
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

斯内克

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.3 （C++代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

【回文数(二)】（C语言代码）

The 3n + 1 problem （C语言代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

迷宫问题（广度优先搜索，巧妙解决越界问题，解析详细易懂）

评论区

精彩推荐

C二级辅导-分段函数（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C二级辅导-计负均正（C语言代码）

程序员的表白（C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C二级辅导-统计字符（C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

【亲和数】（C语言代码）

斯内克

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.3 （C++代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

【回文数(二)】 （C语言代码）

The 3n + 1 problem （C语言代码）

你的开发任务 （C++代码）写到一半，等有心情回来补全

迷宫问题 （广度优先搜索，巧妙解决越界问题，解析详细易懂）

评论区

精彩推荐

C二级辅导-分段函数 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C二级辅导-计负均正 （C语言代码）

程序员的表白 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C二级辅导-统计字符 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

【亲和数】 （C语言代码）

【回文数(二)】（C语言代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

迷宫问题（广度优先搜索，巧妙解决越界问题，解析详细易懂）

　　评论区

C二级辅导-分段函数（C语言代码）

C二级辅导-计负均正（C语言代码）

程序员的表白（C语言代码）

C二级辅导-统计字符（C语言代码）

【亲和数】（C语言代码）