蓝桥杯练习系统(算法训练)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

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务,目标是自动识别图像中的对象类别。通过卷积神经网络(CNN)等深度学习技术,我们可以构建高效的图像分类系统,广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统,包括环境

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

嵌入式QT开发:构建高效智能的嵌入式系统

摘要: 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发,详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程,包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发,涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用,以及嵌入式 QT 与硬件设备的交互,包括输入输出设

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO