算法笔试模拟题精解之“恐怖的辐射”-阿里云开发者社区

开发者社区> 被纵养的懒猫> 正文

算法笔试模拟题精解之“恐怖的辐射”

简介: 因为N M 和最大辐射值都不大,所以可以直接模拟辐射扩散的实际情况,最后判断是否有小于等于7的位置。
+关注继续查看

在线编程介绍

阿里云开发者社区在线编程产品,针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等,界面整洁明了,操作简单,为用户营造专心答题的学习环境。点击链接开始体验:https://developer.aliyun.com/coding

本文为大家介绍其中的第117题:恐怖的辐射 的题目解析,具体如下:

题目描述

题目等级:困难
知识点:广度优先搜索/BFS

查看题目:恐怖的辐射 一天,Codancer突然发现自己身处一个奇怪的世界,他发现世界是一个N*M的矩形,在矩形的某些位置分布着一些恐怖的辐射源,每个辐射源都有相应的辐射等级,经过他的分析,这些辐射源总共有五个等级,分别命名为A-E级,A级辐射等级为15,B级14,C级12,D级7,E级则没有辐射。

奇怪的是,这些辐射源的辐射是沿着曼哈顿距离进行传播的且随曼哈顿距离递增辐射等级递减,并且,他会绕过其他辐射源,辐射源的等级不可叠加,这意味着如果某位置同时处于两个辐射源的影响范围,则他受到的辐射为辐射等级最高的那个。

他知道当辐射等级小于等于7时,他受到的辐射将不会威胁到他的生命。因此,他想要知道,这个世界是否存在一个位置不会威胁到他的生命。

每组数据的第一行和第二行分别为N,M,接下来为N*M的矩阵,'0'代表空的位置,A-E代表辐射源。(1<=N,M<=100)

输出为T行,每行输出"Yes"或"No"。

示例1
输入:
2
3
["0A0","00E"]
输出:
"No"

解题思路

因为N M 和最大辐射值都不大,所以可以直接模拟辐射扩散的实际情况,最后判断是否有小于等于7的位置。

首先把输入的字符串转化为二维数组,每个位置的值为初始的辐射值。同时还要记录辐射源的位置,因为辐射源的辐射值不会被更高辐射覆盖,即使辐射小于等于7也不能生存。

因为小于等于7的辐射就不会致命,而且辐射值最高的辐射源只有15,所以最多只需要遍历8次,也就是说辐射值最高的辐射源7格之外就是安全得了。

遍历时每一格的修改规则。如果是辐射源,则不修改。如果不是,修改规则如下。

用下图的a位置举例,设T(a)为a位置辐射的当前值。
需要对比 T(a) T(b)-1 T(c)-1 T(d)-1 T(e)-1的值,选其中最大的作为a位置的新值。减1,是因为辐射扩散一次减少1。

最后遍历整个地图,判断是否有小于等于7的位置。
时间复杂度O(9*n*m) 第一遍生成初始状态的数组,之后模拟辐射扩散
空间复杂度O(2*m*n)

image.png

看完之后是不是有了想法了呢,快来练练手吧>>查看题目

image.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
NOIP-C++大神培养计划 Step1.1.2基础算法——模拟算法2
大家好,我是小笨笨,今天我们继续来讲解模拟算法。 我们直接上例题! 栗1.1.2-1 洛谷P1014 Cantor表https://www.luogu.org/problemnew/show/P1014题目描述现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。
987 0
求算符文法的FIRSTVT集的算法
原理 数据结构 1 G = {'key':[v1,v2,v3],'key':[v1,v2,v3]}; 2 VN = []; 3 Vt = []; 4 FirstVT = {'key':[v1,v2,v3],'key':[v1,v2,v3]}; 也就是map里放list,同样将文法压缩,对于产生式相同的发到一个map元素里,追加到map元素对应的list后面 算法过程 1、 先求出直接满足A->a 或 A->Ba的文法的A的FIRSTVT集合 2、 扫描FIRSTVT集,将满足蔓延性公式的终结符加到非终结符的FIRSTVT集合中。
979 0
560
文章
1795
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载