迷宫与陷阱（蓝桥杯）

文章目录

• 迷宫与陷阱
• • 问题描述
  • bfs

迷宫与陷阱

问题描述

小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由 N x N 个格子组成的2D迷宫。

小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫，每一步，他可以移动到上下左右相邻的格子中。

迷宫中有些格子小明可以经过，我们用 ‘.’ 表示；有些格子是墙壁，小明不能经过，我们用 ‘#’ 表示。

此外，有些格子上有陷阱，我们用 ‘X’ 表示，除非小明处于无敌状态，否则不能经过；有些格子上有无敌道具，我们用 ‘%’ 表示。

当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续 K 步，之后如果再次到达该格子不会获得无敌状态了。

处于无敌状态时，可以经过有陷阱的格子，但是不会拆除/毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。

给定迷宫，请你计算小明最少经过几步可以离开迷宫？

输入格式
第一行包含两个整数 N 和 K。
以下 N 行包含一个 N x N 的矩阵（矩阵保证左上角和右下角是 ‘.’）。

输出格式
一个整数表示答案。
如果小明不能离开迷宫，输出 -1。

样例输入1

5 3
...XX
##%#.
...#.
.###.
.....

样例输出1

10

数据范围
1 ≤ N ≤ 1000
1 ≤ K ≤ 10

bfs

这段代码是用来解决上述迷宫游戏的问题，实现思路是通过广度优先搜索（BFS）算法。下面是代码的详细注释解释：

#include<bits/stdc++.h>
using namespace std;

struct node {
	int x, y, k; // 用于存储当前节点的位置x,y以及剩余无敌步数k
};

char g[1010][1010]; // 用于存储迷宫信息
int d[1010][1010][11]; // 用于存储到达每个位置的最短步数，最后一维表示剩余无敌步数
queue<node> q; // BFS使用的队列
int dx[4]={-1,1,0,0}; // x方向移动的四个方向：上、下
int dy[4]={0,0,-1,1}; // y方向移动的四个方向：左、右
int n, k; // n表示迷宫的大小，k表示无敌道具的作用步数

// 检查(x,y)位置是否可达，即不是墙壁'#'且在迷宫范围内
bool check(int x,int y) {
	if(x>=0 && x<n && y>=0 && y<n && g[x][y]!='#')
		return true;
	return false;
}

// 广度优先搜索函数，返回从起点到终点的最短步数
int bfs() {
	q.push({0,0,0});
	d[0][0][0] = 0;
	while(q.size()) {
		auto t = q.front(); // 取出队首元素
		q.pop(); // 弹出队首元素
		// 如果到达终点，返回到达终点的步数
		if(t.x==n-1 && t.y==n-1) return d[t.x][t.y][t.k];
		for(int i=0; i<4; i++) { // 遍历四个方向
			int x = t.x + dx[i];
			int y = t.y + dy[i];
			if(check(x,y)) { // 检查新位置是否可达
				// 如果是无敌道具'%'且新位置未被访问，更新状态并加入队列
				if(g[x][y]=='%' && d[x][y][k]==-1) {
					q.push({x,y,k});
					d[x][y][k] = d[t.x][t.y][t.k] + 1;
				}
				// 如果是陷阱'X'，且有无敌状态，且新位置未被访问，更新状态并加入队列
				if(g[x][y]=='X' && t.k && d[x][y][t.k-1]==-1) {
					q.push({x,y,t.k-1});
					d[x][y][t.k-1] = d[t.x][t.y][t.k] + 1;
				}
				// 如果是空地'.'，且有无敌状态，且新位置未被访问，更新状态并加入队列
				if(g[x][y]=='.' && t.k && d[x][y][t.k-1]==-1) {
					q.push({x,y,t.k-1});
					d[x][y][t.k-1] = d[t.x][t.y][t.k] + 1;
				}
				// 如果是空地'.'，且没有无敌状态，且新位置未被访问，更新状态并加入队列
				if(g[x][y]=='.' && t.k==0 && d[x][y][t.k]==-1) {
					q.push({x,y,t.k});
					d[x][y][t.k] = d[t.x][t.y][t.k] + 1;
				}
			}
		}
	}
	// 如果不能到达终点，返回-1
	return -1;
}

int main() {
	cin >> n >> k; // 输入迷宫的大小和无敌步数
	memset(d, -1, sizeof(d)); // 初始化d数组为-1，表示未访问状态
	// 读入迷宫信息
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			cin >> g[i][j];
	// 输出从起点到终点的最短步数
	cout << bfs() << endl;
	return 0;
}

这段代码通过广度优先搜索（BFS）算法，利用队列来探索从起点（左上角）到终点（右下角）的最短路径，同时处理无敌状态和陷阱，从而找出小明离开迷宫的最短步数。