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

蓝桥杯练习系统(算法训练)ALGO-949 勇士和地雷阵

资源限制

内存限制:256.0MB   C/C++时间限制:1.0s   Java时间限制:3.0s   Python时间限制:5.0s

问题描述

  勇士们不小心进入了敌人的地雷阵(用n行n列的矩阵表示,'*'表示某个位置埋有地雷,'-'表示某个位置是安全的),他们各自需要在规定的步数(一步代表走到和当前位置相邻的位置)内绕开地雷到达出口(第一行第一格,即坐标为(0,0)的位置)才能完成任务,告诉你每个勇士的位置(x,y)和规定的步数s,请你判断每个勇士能否顺利完成任务(1代表“能”,-1代表“不能”)。

输入格式

  输入数据的第一行为一个整数n;第二行至第n+1行是n行n列地雷阵的矩阵表示(见输入样例);第n+2行至最后一行每行是一个勇士的位置x、y和到达出口规定的最大步数s,三个整数间用空格隔开。

输出格式

  按顺序输出对每个勇士是否能顺利完成任务的判断(1代表“能”,-1代表“不能”),对每个勇士的判断占一行。

样例输入

5
-----
--*--
-**--
-**--
*-*--
0 1 1
0 4 3
1 1 3
1 4 2
2 0 3
3 0 4
3 3 2
4 1 3

样例输出

1
-1
1
-1
1
1
-1
-1

数据规模和约定

  1≤n≤500,0≤x≤n-1,0≤y≤n-1,1≤s≤500

对每一个要求的判断的点都进行bfs,超时,仅供理解题意

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
const int N=505;
typedef struct point{int x;int y;int step;
}point;int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};int main(){int n;cin>>n;char map[N][N];for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>map[i][j];}}int x,y,num;while(cin>>x>>y>>num){queue<point> q;bool st[N][N];memset(st,0,sizeof(st));point start;start.x=x;start.y=y;start.step=0;q.push(start);//bfswhile(q.size()){point p=q.front();if(p.x==0&&p.y==0){break;}for(int i=0;i<4;i++){int a=p.x+dx[i],b=p.y+dy[i];if(a>=0&&a<n&&b>=0&&b<n&&!st[a][b]&&map[a][b]=='-'){st[a][b]=true;point next;next.x=a,next.y=b,next.step=p.step+1;q.push(next);}}q.pop();}if(q.size()==0){cout<<"-1"<<endl;}else{if(q.front().step<=num){cout<<1<<endl;}else cout<<-1<<endl;}}return 0;
} 

bfs一次

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
const int N=505;
typedef struct point{int x;int y;int step;
}point;int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
char map[N][N];
int dist[N][N];//(0,0)到点的距离,如果无法到达(x,y)点,dist为0 
bool st[N][N];
queue<point> q;
int n;void bfs(){while(q.size()){point p=q.front();for(int i=0;i<4;i++){int a=p.x+dx[i],b=p.y+dy[i];if(a>=0&&a<n&&b>=0&&b<n&&!st[a][b]&&map[a][b]=='-'){st[a][b]=true;point next;next.x=a,next.y=b,next.step=p.step+1;dist[a][b]=p.step+1;q.push(next);}}q.pop();}
}
int main(){cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>map[i][j];}}point start;start.x=0,start.y=0,start.step=0;q.push(start);bfs();int x,y,num;while(cin>>x>>y>>num){//dist为0有两种情况,第一种是真的步数为0,第二种是到不了 if(x==0&&y==0) cout<<1<<endl;//第一种 else{if(dist[x][y]!=0&&dist[x][y]<=num){//在能到的前提下,步长小于等于num 可行 cout<<1<<endl; }else cout<<-1<<endl;}}return 0;
} 

思路:在判断之前,可以求出(0,0)到其他任何点的步数 ,存在dist数组中,然后对每一个点进行判断。

相关文章:

蓝桥杯练习系统(算法训练)ALGO-949 勇士和地雷阵

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 问题描述 勇士们不小心进入了敌人的地雷阵&#xff08;用n行n列的矩阵表示&#xff0c;*表示某个位置埋有地雷&#xff0c;-表示某个…...

腾讯安全客户端(电脑管家部门)一面

上来介绍部门&#xff0c;之后自我介绍 说了是个喜欢每天都学点新东西的人&#xff0c;然后平常也会在课余时间之外去做点项目方面的学习&#xff0c;比如Web项目做出来就是因为兴趣。喜欢结构性的东西&#xff0c;有一门课叫电路电子学一次考试是专业第二。其他也都还可以&am…...

激励与关怀并行:员工工作动力倍增之道

在现代企业中&#xff0c;员工是推动公司发展的核心力量。如何激发员工的工作动力&#xff0c;使他们在工作中发挥出最大的潜力&#xff0c;一直是企业管理者关注的焦点。实际上&#xff0c;激励与关怀并行的策略&#xff0c;是一种非常有效的提升员工工作动力的方法。 激励是激…...

软件系统安全设计规范(word原件)

1.1安全建设原则 1.2 安全管理体系 1.3 安全管理规范 1.4 数据安全保障措施 1.4.1 数据库安全保障 1.4.2 操作系统安全保障 1.4.3 病毒防治 1.5安全保障措施 1.5.1实名认证保障 1.5.2 接口安全保障 1.5.3 加密传输保障 1.5.4终端安全保障 软件资料清单列表部分文档…...

做题速度太慢了,面不上

没办法&#xff0c;之前练了一个月的sql。两个月不写&#xff0c;现在差不多忘干净了。工作空窗期&#xff0c;或者休息期不能太久&#xff0c;不然学再多的内容都可能会忘完的。 sql题&#xff0c;腾讯四道sql题&#xff0c;限时45分钟完成。我只做了一道&#xff0c;还没做完…...

Vue 路由

单应用程序 SPA - Single Page Application 所有功能在一个html页面上实现 单页面应用 多用于 系统类网站/内部网站/文档类网站/移动端站点 多页面应用 多用于 公司官网/电商类网站 路由 单页面应用按需更新页面&#xff0c;需要明确访问路径和组件的对应关系 Vue中的路…...

docker-compose-itd和d

docker run -itd和-d的区别 前言&#xff1a; ​ 今天在通过docker-compose启动一基于ubuntu的镜像容器时&#xff0c;发现启动后&#xff0c;容器会一直停止。但是通过docker run -itd是可以正常运行的。基于这个区别&#xff0c;找了一位大神&#xff08;师傅&#xff09;问…...

WordPress MasterStudy LMS插件 SQL注入漏洞复现(CVE-2024-1512)

0x01 产品简介 WordPress和WordPress plugin都是WordPress基金会的产品。WordPress是一套使用PHP语言开发的博客平台。该平台支持在PHP和MySQL的服务器上架设个人博客网站。WordPress plugin是一个应用插件。 0x02 漏洞概述 WordPress Plugin MasterStudy LMS 3.2.5 版本及之…...

初识Vue-组件通信(详解props和emit)

目录 一、组件通信介绍 1.概念 2.作用 3.特点 4.应用 二、组件通信语法 1.Props 1.1.在子组件中声明 props 1.2.在父组件中传递数据 2.Emit 2.1.在子组件中触发事件 2.2.在父组件中监听事件 三、应用实例 1. 购物车组件 2. 表单数据处理 四、总结 一、组件通信介…...

二叉树的前序、中序、后序遍历的C++实现

二叉树的前序、中序、后序 遍历属于深度优先搜索方式&#xff0c;本文使用递归法实现前序、中序、后序的遍历方法&#xff0c;代码如下&#xff1a; #include <iostream> #include <vector>struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int …...

golang中数组array和切片slice的区别

go语言中最常用的数据结构 数组array 和 切片 slice的区别对比&#xff1a; 定义和初始化&#xff1a; 数组&#xff1a; [size]类型 切片&#xff1a; []类型 &#xff0c; 数组变量[low:high] var arr1 [3]string{"a", "b", "c"} //…...

LSM-Tree 原理分析

深入浅出分析LSM树&#xff08;日志结构合并树&#xff09; - 知乎 写得太好了&#xff0c;留下记录。便于复习。 LSM树详解 - 知乎 多了点点内容&#xff0c;也看看吧。...

【代码随想录37期】Day01 二分查找 + 移除元素

二分查找 力扣704 贴一下之前的笔记&#xff1a; 没想到一下子写不出来&#xff0c;忘记什么是二分法了&#xff0c;这里回顾一下&#xff1a; 「二分查找 binary search」是一种基于分治策略的高效搜索算法。 它利用数据的有序性&#xff0c;每轮减少一半搜索范围&#xff…...

GitPython 使用教程

GitPython 使用教程 GitPython 是一个用于与 Git 版本控制系统进行交互的 Python 库。它提供了简单的接口&#xff0c;让你可以通过 Python 代码执行 Git 命令和操作 Git 仓库。 1. 安装 GitPython 你可以使用 pip 在命令行中安装 GitPython&#xff1a; pip install gitpy…...

MATLAB 基于规则格网的点云抽稀方法(自定义实现)(65)

MATLAB 基于规则格网的点云抽稀方法(自定义实现)(65) 一、算法介绍二、算法实现1.代码2.结果一、算法介绍 海量点云的处理,需要提前进行抽稀预处理,相比MATLAB预先给出的抽稀方法,这里提供一种基于规则格网的自定义抽稀方法,步骤清晰,便于理解抽稀内涵, 主要涉及到使…...

论文阅读】 ICCV-2021-3D Local Convolutional Neural Networks for Gait Recognition

motivation :现有方法方法无法准确定位身体部位&#xff0c;不同的身体部位可以出现在同一个条纹(如手臂和躯干)&#xff0c;一个部分可以出现在不同帧(如手)的不同条纹上。其次&#xff0c;不同的身体部位具有不同的尺度&#xff0c;即使是不同帧中的同一部分也可以出现在不同…...

同一局域网如何从Windows系统拷贝文件到银河麒麟系统

1. 先将Windows下的、被拷贝文件所在文件夹设置为共享目录&#xff1a;在文件夹上单击右键选择“属性”菜单&#xff0c;弹出如下对话框&#xff1a; 按数字顺序单击鼠标左键&#xff0c;弹出如下对话框&#xff1a; 并将权限开放为Everyone&#xff0c;单击“共享”按钮。 在…...

2024年华为OD机试真题-数的分解-(C++)-OD统一考试(C卷D卷)

题目描述: 给定一个正整数n,如果能够分解为m(m > 1)个连续正整数之和,请输出所有分解中,m最小的分解。 如果给定整数无法分解为连续正整数,则输出字符串"N"。 输入描述: 输入数据为一整数,范围为(1, 2^30] 输出描述: 比如输入为: 21 输出: 21=10+11 补…...

vue-img-cutter 图片裁剪详解

前言&#xff1a;vue-img-cutter 文档&#xff0c;本文档主要讲解插件在 vue3 中使用。 一&#xff1a;安装依赖 npm install vue-img-cutter # or yarn add vue-img-cutter # or pnpm add vue-img-cutter 二&#xff1a;构建 components/ImgCutter.vue 组件 <script se…...

PCL 点云中的平面点云提取

平面点云提取 一. 索引提取1.1 算法概念1.2 算法流程1.3 主要函数二.代码示例三.结果示例一. 索引提取 1.1 算法概念 平面点云提取:是指从点云数据中提取出属于平面的点的过程。 1.2 算法流程 使用pcl::SACSegmentation类进行点云分割的基本步骤如下: 创建一个pcl::SACSegm…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

Matlab实现任意伪彩色图像可视化显示

Matlab实现任意伪彩色图像可视化显示 1、灰度原始图像2、RGB彩色原始图像 在科研研究中&#xff0c;如何展示好看的实验结果图像非常重要&#xff01;&#xff01;&#xff01; 1、灰度原始图像 灰度图像每个像素点只有一个数值&#xff0c;代表该点的​​亮度&#xff08;或…...

命令行关闭Windows防火墙

命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)​方法二:CMD命令…...

中国政务数据安全建设细化及市场需求分析

(基于新《政务数据共享条例》及相关法规) 一、引言 近年来,中国政府高度重视数字政府建设和数据要素市场化配置改革。《政务数据共享条例》(以下简称“《共享条例》”)的发布,与《中华人民共和国数据安全法》(以下简称“《数据安全法》”)、《中华人民共和国个人信息…...