P8673 [蓝桥杯 2018 国 C] 迷宫与陷阱

题目描述

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

小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。

每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。

迷宫中有些格子小明可以经过，我们用 . 表示；

有些格子是墙壁，小明不能经过，我们用 # 表示。

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

有些格子上有无敌道具，我们用 % 表示。

当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续 $K$ 步。

之后如果再次到达该格子不会获得无敌状态了。

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

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

输入格式

第一行包含两个整数 $N$ 和 $K$。$(1\le N\le 1000，1\le K\le 10)$。

以下 $N$ 行包含一个 $N\times N$ 的矩阵。

矩阵保证左上角和右下角是 .。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

10

输入输出样例 #2

输入 #2

5 1
...XX
##%#.
...#.
.###.
.....

输出 #2

12

说明/提示

时限 3 秒, 256M。蓝桥杯 2018 年第九届国赛

C++实现

#include<bits/stdc++.h>
using namespace std;
struct edge{
	int x,y,invincible,sum;
};
int n,x,nx[] = {0,0,1,-1},ny[] = {1,-1,0,0},book[1001][1001];
char a[1001][1001];
queue<edge>q; //建立结构体数组
int main(){
	cin >> n >> x;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++) cin >> a[i][j],book[i][j] = -1;  
	edge t;
	t.x = 1,t.y = 1,t.invincible = 0,t.sum = 0;
	q.push(t);
	book[1][1] = 0; //初始位置入队，标记初始点为0（剩余无敌步数为0）
	while(!q.empty()){
		t = q.front();
		q.pop();
		if(t.x == n && t.y == n) return cout << t.sum,0;
		edge k;
		for(int i = 0;i < 4;i++){
			int dx,dy;
			dx = t.x + nx[i];
			dy = t.y + ny[i];  //计算下一步
			if(a[dx][dy] == 'X' && t.invincible == 0) continue;  
			if(a[dx][dy] == '#') continue;
			k.invincible = max(0,t.invincible - 1); //无敌步数是上一步-1
			if(a[dx][dy] == '%') k.invincible = x;  //如果当前还是无敌道具，重置无敌步数
			if(dx >= 1 && dx <= n && dy >= 1 && dy <= n && k.invincible > book[dx][dy]){  
				k.x = dx;
				k.y = dy;
				book[dx][dy] = k.invincible;
				k.sum = t.sum + 1;
				q.push(k);
			}
		}
	}
	cout << "-1";
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容