RioTian

用户名：jiahe

访问量：34652

签　名：

2021加油

等　　级
排　　名	76
经　　验	9895
参赛次数	2
文章发表	78
年　　龄	0
在职情况	学生
学　　校	XX理工大学
专　　业	软件工程

　　自我简介：

个人博客：https://www.cnblogs.com/RioTian/

TA的其他文章

Kanna-Hello, world! （两种方法，都比较简单）
浏览：1417

Kanna-【出圈】-（38行代码解决问题）
浏览：526

Kanna-字符串编辑--string灵活使用
浏览：259

你可能喜欢

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

Kanna-迷宫问题--BFS(注释思路清晰）

　　作者: RioTian　　　　发表时间：2020-02-01 09:43:07 浏览：425　|　评论：0　

原题链接：迷宫问题

#include<iostream>
    using namespace std;
    //node结构体存储坐标与步数
    struct node {
    	int x, y;
    	int s;//走过的步数
    };
    
    int n, m;
    int head, tail;//用head，tail模拟队列，head++表示出列，tail++表示入队
    int sx, sy, p, q, tx, ty;//sx,xy起点的坐标，p、q终点坐标，tx和ty存储移动以后的临时坐标
    
    int main()
    {
    	char a[105][105];//迷宫大小，用char存储
    	int c;
    	cin >> c;
    	while (c--)
    	{
    
    		struct node que[2501] = { 0 };
    		int book[105][105] = { 0 };
    		cin >> n >> m;//记录输入迷宫行列大小
    		for (int i = 1; i <= n; ++i)
    			for (int j = 1; j <= m; ++j)
    			{
    				cin >> a[i][j];
    				if (a[i][j] == 'S')
    				{
    					sx = i;
    					sy = j;
    				}
    				if (a[i][j] == 'E')
    				{
    					p = i;
    					q = j;
    				}
    			}
    		//初始化起点坐标，将坐标存储在que[tail](que[1]）中
    		head = tail = 1;
    		que[tail].x = sx;
    		que[tail].y = sy;
    		que[tail].s = 0;
    		tail++;
    		book[sx][sy] = 1;
    
    		//每一步的方向数组
    		int next[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
    
    		int flag = 0;
    		while (head < tail)
    		{
    			for (int 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 (book[tx][ty] == 0 && a[tx][ty] == '-' || a[tx][ty] == 'E')
    				{
    					book[tx][ty] = 1;
    					que[tail].x = tx;
    					que[tail].y = ty;
    					que[tail].s = que[head].s + 1;//这个点是由head点移动而来的，所以步数上是que[head].s+1
    					tail++;
    				}
    				//判断是否已经到达终点
    				if (tx == p && ty == q)
    				{
    					//这里顺序不能错
    					flag = 1;
    					break;
    				}
    			}
    			if (flag == 1)
    				break;
    			head++;//这里千万不能忘记，在我们遍历了que[head]的点的四个方向的情况以后就用不到了，所以head++移向它的子坐标
    
    		}
    		if (flag == 1)
    			//注意在结束循环以后tail是指向最后终点的下一个位置的，所以需要我们tail-1才能正确表示
    			cout << que[tail - 1].s << endl;
    		else
    			cout << -1 << endl;
    	}
    	return 0;
    }

0.0分

4 人评分

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

RioTian

TA的其他文章

你可能喜欢

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

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

逆反的01串（C++代码）（依旧推荐switch）

输出正反三角形（C语言代码）

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

Kanna-迷宫问题--BFS(注释思路清晰）

评论区

精彩推荐

【绝对值排序】（C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

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

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

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

众数问题（C语言代码）

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

小O的乘积（C++代码）

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

求圆的面积（C语言代码）

RioTian

TA的其他文章

你可能喜欢

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

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

逆反的01串 （C++代码）（依旧推荐switch）

输出正反三角形 （C语言代码）

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

Kanna-迷宫问题--BFS(注释思路清晰）

评论区

精彩推荐

【绝对值排序】 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

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

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

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

众数问题 （C语言代码）

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

小O的乘积 （C++代码）

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

求圆的面积 （C语言代码）

逆反的01串（C++代码）（依旧推荐switch）

输出正反三角形（C语言代码）

　　评论区

【绝对值排序】（C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

众数问题（C语言代码）

小O的乘积（C++代码）

求圆的面积（C语言代码）