当前位置: 首页 > news >正文

迷宫与陷阱(蓝桥杯)

文章目录

  • 迷宫与陷阱
    • 问题描述
    • 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)算法。下面是代码的详细注释解释:

#include<bits/stdc++.h>
using namespace std;struct node {int x, y, k; // 用于存储当前节点的位置x,y以及剩余无敌步数k
};char g[1010][1010]; // 用于存储迷宫信息
int d[1010][1010][11]; // 用于存储到达每个位置的最短步数,最后一维表示剩余无敌步数
queue<node> 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(x>=0 && x<n && y>=0 && y<n && 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.x==n-1 && t.y==n-1) return d[t.x][t.y][t.k];for(int i=0; i<4; 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.k==0 && 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)算法,利用队列来探索从起点(左上角)到终点(右下角)的最短路径,同时处理无敌状态和陷阱,从而找出小明离开迷宫的最短步数。

http://www.lryc.cn/news/325974.html

相关文章:

  • Temple of Doom靶场nodejs获取shellss-manager漏洞tcpdump提权
  • day03_mysql_课后练习 - 参考答案
  • creator-webview与Android交互
  • 22.WEB渗透测试-BurpSuite(一)
  • 前端性能优化:防抖与节流
  • Copilot 编程助手的介绍及使用
  • 数据库专题(oracle基础和进阶)
  • web蓝桥杯2022省赛真题:水果拼盘
  • Web核心
  • iOS应用审核问题解决方案及优化方法 ✨
  • java post、get请求第三方https接口
  • 【C语言】鸡兔同笼,鸡和兔共 100 只,共 284 只脚,求鸡和兔的个数。
  • 沪漂8年回郑州三年如何走上创业之路
  • MySQL数据库—事务与存储类型
  • 蓝桥杯刷题8
  • Java中的String字符串练习
  • 基于JavaWeb SSM mybatis 学生信息管理系统设计和实现以及文档报告
  • 二进制源码部署mysql8.0.35
  • PHP 读取嵌入式数据 SQLite3
  • 【代驾+顺风车+货运】全开源双端APP代驾+顺风车+货运代驾小程序源码
  • C++语言学习(三)—— 文件操作
  • linux文本三剑客 --- grep、sed、awk
  • leetcode 107.二叉树的层序遍历II
  • Java生成唯一ID的方式有哪些?
  • 代码随想录day44:动态规划over,回文子串及字序列
  • ElasticSearch启动报错:Exception in thread “main“ SettingsException
  • git配置密钥
  • Pandas库常用方法、函数集合
  • Qt实现TFTP Server和 TFTP Client(一)
  • MySQL数据库的日志管理以及备份和恢复