首页 > 编程语言 >算法题 逃离迷宫

算法题 逃离迷宫

时间:2023-09-04 13:07:24浏览次数:40  
标签:end int 迷宫 step next 逃离 算法 array


 题目描述:

你在一个地下迷宫中找到了宝藏,但是也触发了迷宫机关,导致迷宫将在T分钟后坍塌,为此你需要在T分钟内逃离迷宫,你想知道你能不能逃离迷宫。迷宫是一个边长为m的正方形,其中"S"表示你所在的位置,"E"表示迷宫出口,"."是可以随意走动的区域,"#"是不可穿行的墙壁,每次你可以耗费1分钟在区域间移动(上下左右四个方向)。

输入描述:

输入包含多组数组,第一行是一个整数K(1<=K<=10),表示有K组数据。接下来每组数包含整数m(2<=m<=10)和整数T,m表示正方形迷宫的边长,T表示坍塌时间。其后是一个m*m的字符矩阵,包含字符"S", "E", "."和"#"。

输出描述:

每组数据输出一行,输出“YES"或者"NO",表示是否可以在坍塌之前逃离(也就是说移动次数是否可以不超过T)。

样例输入:

样例输出:

2

4 7

S...

###.

.#E.

..#.

3 4

S..

..#

.#E

YES

NO

#include<iostream>
using namespace std;
#include<cstring>
#include<algorithm>
#include <queue>


struct node
{
	int x, y, step;
};

int xarray[4] = { 1,0,-1,0 };		//  右  下  左  上
int yarray[4] = { 0,1,0,-1 };




void BFS(node start, node& end, char array[12][12], bool flag[20][20]) {

	queue<node>q;
	q.push(start);
	while (!q.empty())
	{
		node temp = q.front();

		if (temp.x == end.x && temp.y == end.y)
		{
			end.step = temp.step;
			break;
		}
		else
		{
			q.pop();
			node next;
			for (int i = 0; i < 4; i++)
			{
				next.x = temp.x + xarray[i];
				next.y = temp.y + yarray[i];
				if (array[next.x][next.y] != '#' && !flag[next.x][next.y])
				{
					next.step = temp.step + 1;
					q.push(next);
					flag[next.x][next.y] = true;
				}
			}
		}
	}
}

int main()
{

	int numbers;	cin >> numbers;
	while (numbers--)
	{
		int js; cin >> js;
		int time;	cin >> time;

		bool flag[20][20] = { false };

		node start;
		node end;

		char array[12][12];
		for (int r = 0; r < 12; r++)
		{
			fill(array[r], array[r] + 12, '#');
		}
		//	对迷宫的赋值
		for (int r = 1; r < js + 1; r++)
		{
			for (int c = 1; c < js + 1; c++)
			{
				cin >> array[r][c];
				if (array[r][c] == 'S')
				{
					start.x = r;	start.y = c;	start.step = 0;
				}
				if (array[r][c] == 'E')
				{
					end.x = r;	end.y = c; end.step = 0;
				}
			}
		}
		BFS(start, end, array, flag);
		if (end.step != 0 && end.step <= time)
		{
			cout << "YES";
		}
		else
		{
			cout << "NO";
		}
	}
}

算法题 逃离迷宫_#include



标签:end,int,迷宫,step,next,逃离,算法,array
From: https://blog.51cto.com/u_16003019/7347698

相关文章

  • Bresenham算法画圆
    目录问题背景Bresenham算法画圆算法推演算法步骤算法程序参考问题背景如何在屏幕上绘制一个圆?可以先看看圆的特性,根据其特性决定如何绘制。。圆的特性圆定义:所有距离中心位置(xc,yc)为给定值r的点集。圆的方程:\[(x-x_c)^2+(y-y_c)^2=r^2\tag{1}\]根据圆的方程绘制圆......
  • 机器学习算法编程小技巧——numpy用法之np.c_
     importnumpyasnp#创建两个一维数组a=np.array([1,2,3])b=np.array([4,5,6])#使用numpy.c_将它们连接在一起"""numpy.c_是一个方便的工具,用于沿第二轴连接数组。它将数组转换为至少2-D,并将它们堆叠在一起。这在需要将多个数组组合成一个更大数组的情况......
  • Lnton羚通智能分析算法车辆拥堵智能识别检测
    车辆拥堵智能识别是基于图像处理和计算机视觉技术,通过分析道路交通图像或视频信息,实时检测和识别交通拥堵状况的一种方法。车辆拥堵智能识别算法包括以下几种常见的方法和技术:1.基于图像处理的拥堵识别:通过分析交通监控摄像头拍摄到的道路图像,利用图像处理和计算机视觉技术来检测和......
  • 2023“钉耙编程”中国大学生算法设计超级联赛(3)
    1005.OutofControl题意:有n个数\(x_1,x_2,...,x_n\),在其中选k个数依次放入栈中。如果当前放入栈中的数\(x_i\)小于栈顶的数,则向栈中放入与先前的栈顶相同的数而不是\(x_i\)。求对于每个k对应的方案数。分析:先排序离散化,然后考虑dp。状态定义:f[i][j]表示长度为i且最后一个......
  • 代码随想录算法训练营第二十九天| 491.递增子序列 46.全排列 47.全排列 II
     491.递增子序列   卡哥建议:本题和大家刚做过的 90.子集II 非常像,但又很不一样,很容易掉坑里。 https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html  视频讲解:https://www.bilibili.com/video/BV1EG4y1h78v  做题思路......
  • 代码随想录算法训练营第三十天| 51. N皇后 37. 解数独 总结
        卡哥建议:今天这三道题都非常难,那么这么难的题,为啥一天做三道? 因为 一刷 也不求大家能把这么难的问题解决,所以 大家一刷的时候,就了解一下题目的要求,了解一下解题思路,不求能直接写出代码,先大概熟悉一下这些题,二刷的时候,随着对回溯算法的深入理解,再去解决如下三题。 ......
  • Dubbo(六)_时间轮算法
    时间轮算法介绍HashedWheelTimer定时轮算法在netty、dubbo等框架中运用广泛。比如在Dubbo中为了增强系统的容错能力,会有相应的监听判断机制比如RPC调用超时机制,消费者判断请求是否超时,如果超时就将结果返回给应用层。初期Dubbo实现时采取将所有返回的结果DefaultFutu......
  • MD5算法原理(未完成)
    MD5简介MD5不是一种加密算法,而是一种哈希算法,用于生成固定长度的哈希值。哈希算法通常不涉及加密或解密,它们是单向操作,将输入数据转换为固定长度的哈希值,而无法从哈希值还原原始数据。MD5算法核心步骤:填充数据:首先,将输入数据填充到长度为512位的多重数(multipleof512bits),......
  • Lnton羚通算法算力云平台【PyTorch】教程:torch.nn.Hardtanh
    torch.nn.Hardtanh原型CLASStorch.nn.Hardtanh(min_val=-1.0,max_val=1.0,inplace=False,min_value=None,max_value=None)参数min_val ([float])–线性区域的最小值,默认为-1max_val ([float])–线性区域的最大值,默认为1inplace ([bool])–默认为Falsetorch.nn.Ha......
  • 五、调度算法
    1、进程调度算法也称CPU调度算法,因为进程由CPU调度。当CPU空闲时选择某个就绪状态的进程并给其分配CPU发生CPU调度的常见情况:进程从运行状态转到等待状态进程从运行状态转到就绪状态进程从等待状态转到就绪状态进程从运行状态到终止状态1和4两种情况下的调度称为非抢占式......