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

2024-05-04 08:04

本文主要是介绍蓝桥杯练习系统(算法训练)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 勇士和地雷阵的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/958720

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Linux系统之主机网络配置方式

《Linux系统之主机网络配置方式》:本文主要介绍Linux系统之主机网络配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、查看主机的网络参数1、查看主机名2、查看IP地址3、查看网关4、查看DNS二、配置网卡1、修改网卡配置文件2、nmcli工具【通用

Linux系统之dns域名解析全过程

《Linux系统之dns域名解析全过程》:本文主要介绍Linux系统之dns域名解析全过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、dns域名解析介绍1、DNS核心概念1.1 区域 zone1.2 记录 record二、DNS服务的配置1、正向解析的配置

Linux系统中配置静态IP地址的详细步骤

《Linux系统中配置静态IP地址的详细步骤》本文详细介绍了在Linux系统中配置静态IP地址的五个步骤,包括打开终端、编辑网络配置文件、配置IP地址、保存并重启网络服务,这对于系统管理员和新手都极具... 目录步骤一:打开终端步骤二:编辑网络配置文件步骤三:配置静态IP地址步骤四:保存并关闭文件步骤五:重

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Linux系统之authconfig命令的使用解读

《Linux系统之authconfig命令的使用解读》authconfig是一个用于配置Linux系统身份验证和账户管理设置的命令行工具,主要用于RedHat系列的Linux发行版,它提供了一系列选项... 目录linux authconfig命令的使用基本语法常用选项示例总结Linux authconfi

Nginx配置系统服务&设置环境变量方式

《Nginx配置系统服务&设置环境变量方式》本文介绍了如何将Nginx配置为系统服务并设置环境变量,以便更方便地对Nginx进行操作,通过配置系统服务,可以使用系统命令来启动、停止或重新加载Nginx... 目录1.Nginx操作问题2.配置系统服android务3.设置环境变量总结1.Nginx操作问题

CSS3 最强二维布局系统之Grid 网格布局

《CSS3最强二维布局系统之Grid网格布局》CS3的Grid网格布局是目前最强的二维布局系统,可以同时对列和行进行处理,将网页划分成一个个网格,可以任意组合不同的网格,做出各种各样的布局,本文介... 深入学习 css3 目前最强大的布局系统 Grid 网格布局Grid 网格布局的基本认识Grid 网