蓝桥杯2018年第九届真题-迷宫与陷阱-题解（C++代码）

1123 阅读 1 评论 0 点赞

原题链接：蓝桥杯2018年第九届真题-迷宫与陷阱

#### 看见最短路径立马想到了BFS，不同的是添加了陷阱和无敌状态，无敌状态的时间是十步以内，数据量小， 在VIS数组中增加一维去特判无敌状态就行，具体步骤在代码中添加注释
```cpp
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 1e3 + 10;
int n, k;
char mp[N][N];
bool vis[N][N][11];
int ans;
int ax[4] = {0, 1, 0, -1};
int ay[4] = {1, 0, -1, 0};
struct node {
	//结构体定义状态， x, y 为状态， k为当前剩余的无敌时间，
	//s为到达这个状态的步数
	int x, y, k, s;
	node (int cx, int cy, int ck, int cs) {
		x = cx, y = cy, k = ck, s = cs;
	}
};
int bfs() {
	queue<node> que;
	//初始化(0, 0)点
	vis[0][0][0] = true;
	que.push(node(0, 0, 0, 0));
	while (!que.empty()) {
	//取出队头元素
		node u = que.front();
		que.pop();
		//到达终点，返回答案
		if (u.x == n - 1 && u.y == n - 1) {
			return u.s;
		}
		//遍历上下左右四个点
		for (int i = 0; i < 4; i++) {
			int tx = u.x + ax[i];
			int ty = u.y + ay[i];
			//越界或者为墙壁，不可达
			if (tx < 0 || ty < 0 || tx >= n || ty >= n || mp[tx][ty] == '#') {
				continue;
			}
			//(tx, ty)处有一个无敌道具， 且此状态未访问过
			if (mp[tx][ty] == '%' && !vis[tx][ty][k]) {
				vis[tx][ty][k] = true;
				que.push(node(tx, ty, k, u.s + 1));
			} else {
			//当前无敌，无论前方是陷阱还是道路都可走
				if (u.k && !vis[tx][ty][u.k - 1]) {
					vis[tx][ty][u.k - 1] = true;
					que.push(node(tx, ty, u.k - 1, u.s + 1));
				//当前不无敌， 而且前方为道路
				} else if (mp[tx][ty] == '.' && !u.k && !vis[tx][ty][0]) {
					vis[tx][ty][0] = true;
					que.push(node(tx, ty, 0, u.s + 1));
				}
			}
		}
	}
	//可到达的遍历完了但是仍然没有到达终点，表示不可达，返回-1
	return -1;	
}
int main() {
	scanf("%d%d", &n, &k);	//读入图的大小和无敌时间
	for (int i = 0; i < n; i++) {	//输入图
		scanf("%s", mp[i]);
	}
	ans = bfs();	//调用BFS函数求解，无解时返回-1
	cout << ans;
	return 0;
}
```

0.0分

6 人评分

本文分类：题解列表
浏览次数：1123 次浏览
发布日期：2020-11-10 15:56:13
本文链接：https://blog.dotcpp.com/a/73686

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

蓝桥杯2018年第九届真题-迷宫与陷阱-题解（C++代码）

评论列表共有 1 条评论

发表评论取消回复

蓝桥杯2018年第九届真题-迷宫与陷阱-题解（C++代码）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 1 条评论

发表评论 取消回复

评论列表共有 1 条评论

发表评论取消回复