网页设计网站开发需要什么,网站开通银行支付接口,网站建设论文题目,宁波seo外包推广软件文章目录 迷宫与陷阱问题描述bfs解题思路代码 迷宫与陷阱
问题描述
小明在玩一款迷宫游戏#xff0c;在游戏中他要控制自己的角色离开一间由 N x N 个格子组成的2D迷宫。
小明的起始位置在左上角#xff0c;他需要到达右下角的格子才能离开迷宫#xff0c;每一步#xf… 文章目录 迷宫与陷阱问题描述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
解题思路
在之前那题迷宫蓝桥杯——DFS和BFS的基础上本题加了很多特殊的情况逐一判断即可。
注意d标记标记数组表示是否已该能量值到达过该点并存储到达每个位置的最短步数。
代码
这段代码是用来解决上述迷宫游戏的问题实现思路是通过广度优先搜索BFS算法。下面是代码的详细注释解释
#includebits/stdc.h
using namespace std;struct node {int x, y, k; // 用于存储当前节点的位置x,y以及剩余无敌步数k
};char g[1010][1010]; // 用于存储迷宫信息
int d[1010][1010][11]; // 用于存储到达每个位置的最短步数最后一维表示剩余无敌步数
queuenode 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(x0 xn y0 yn 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.xn-1 t.yn-1) return d[t.x][t.y][t.k];for(int i0; i4; 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.k0 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;}}}}// 如果不能到达终点返回-1return -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算法利用队列来探索从起点左上角到终点右下角的最短路径同时处理无敌状态和陷阱从而找出小明离开迷宫的最短步数。
