lw

用户名：saudade

访问量：12528

签　名：

等　　级
排　　名	176
经　　验	6710
参赛次数	23
文章发表	25
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

矩阵嵌套-题解（C++代码）dp最长上升子序列问题的变形
浏览：275

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

蓝桥杯2015年第六届真题-广场舞-题解（C++代码）
浏览：321

你可能喜欢

A+B for Input-Output Practice (V) （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

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

　　作者: lw　　　　发表时间：2020-11-10 15:56:13 浏览：907　|　评论：1　

原题链接：蓝桥杯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分

44 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

春风

请问像这样搜索完了确实会出现一个结果，但为什么一定是最优结果呢（最少经过几步可以离开迷宫）？从给出的示例中就可以看到，在经过无敌道具后向下走也是走的通的，不过这种情况是12步，而遇到无敌道具后向上折返穿越陷阱是10步，我就是想问一下输出的为什么只是10而不是12，或者说不包括12呢？

2023-03-13 21:02:47

lw

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (V) （C语言代码）

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

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

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

A+B for Input-Output Practice (III) （C语言代码）

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

评论区

精彩推荐

C语言训练-委派任务* （C语言代码）..................竟然是第一个

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

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

C语言训练-列出最简真分数序列* （C语言代码）

ASCII帮了大忙

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

完数（C语言代码）

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

陶陶摘苹果2 （C语言代码）

最好的，

lw

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (V) （C语言代码）

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

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

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

A+B for Input-Output Practice (III) （C语言代码）

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

评论区

精彩推荐

C语言训练-委派任务* （C语言代码）..................竟然是第一个

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

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

C语言训练-列出最简真分数序列* （C语言代码）

ASCII帮了大忙

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

完数 （C语言代码）

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

陶陶摘苹果2 （C语言代码）

最好的，

　　评论区

完数（C语言代码）