lw

用户名：saudade

访问量：12653

签　名：

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

　　自我简介：

TA的其他文章

信息学奥赛一本通T1251-仙岛求药-题解（C++代码）
浏览：1124

防御导弹-题解（C++代码）
浏览：436

得得得得得
浏览：222

你可能喜欢

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

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

　　作者: lw　　　　发表时间：2020-11-10 15:56:13 浏览：914　|　评论：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 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

春风

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

2023-03-13 21:02:47

lw

TA的其他文章

你可能喜欢

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

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

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

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

点我有惊喜！你懂得！

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

评论区

精彩推荐

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

钟神赛车（C语言代码）

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

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

1048题解（读入回车问题）

时间转换（C语言代码）

找出最长的字符串来（C语言代码）

数列问题（C语言代码）

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

多组数据新方法

lw

TA的其他文章

你可能喜欢

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

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

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

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

点我有惊喜！你懂得！

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

评论区

精彩推荐

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

钟神赛车 （C语言代码）

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

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

1048题解（读入回车问题）

时间转换 （C语言代码）

找出最长的字符串来 （C语言代码）

数列问题 （C语言代码）

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

多组数据新方法

　　评论区

钟神赛车（C语言代码）

时间转换（C语言代码）

找出最长的字符串来（C语言代码）

数列问题（C语言代码）