算法笔试模拟题精解之“恐怖的辐射”
算法笔试模拟题精解之“恐怖的辐射”
贡献者 | 黄信旭
简介：因为 N M 和最大辐射值都不大，所以可以直接模拟辐射扩散的实际情况，
最后判断是否有小于等于 7 的位置。
题目描述
题目等级：困难
知识点：广度优先搜索 /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。
时间复杂度 O(9*n*m) 第一遍生成初始状态的数组，之后模拟辐射扩散
空间复杂度 O(2*m*n)
看完之后是不是有了想法了呢，快来练练手吧 >> 查看题目
全站分卷索引 · 74 卷
- 1一、算法思想
- 2算法笔试模拟题精解之“打怪兽”
- 31.2 贪心
- 4算法笔试模拟题精解之“最强的团队”
- 5算法笔试模拟题精解之“Tom 爱吃巧克力”
- 6算法笔试模拟题精解之“吃奶酪”
- 7算法笔试模拟题精解之“一的个数”
- 8算法笔试模拟题精解之“Bob 的花束”
- 9算法笔试模拟题精解之“钱庄”
- 10算法笔试模拟题精解之“移动射击”
- 11算法笔试模拟题精解之“相似数组”
- 12算法笔试模拟题精解之“过吊桥”
- 13算法笔试模拟题精解之“完美排列”
- 14算法笔试模拟题精解之“采摘圣诞果”
- 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
- 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
- 17算法笔试模拟题精解之“学习小组”
- 18算法笔试模拟题精解之“恢复字符串”
- 191.3 DP/ 动态规划
- 20算法笔试模拟题精解之“寻找等比数列”
- 21算法笔试模拟题精解之“字符配对”
- 22算法笔试模拟题精解之“数组染色”
- 23算法笔试模拟题精解之“连绵的群山”
- 24算法笔试模拟题精解之“难住Tom 的问题”
- 25算法笔试模拟题精解之“变化的字符”
- 26算法笔试模拟题精解之“跳房子”
- 27算法笔试模拟题精解之“寒假活动”
- 28算法笔试模拟题精解之“最短路”
- 29算法笔试模拟题精解之“codancer 上楼”
- 30算法笔试模拟题精解之“木棒拼接”
- 31算法笔试模拟题精解之“Codancer 的数组封印”
- 32算法笔试模拟题精解之“Jerry 的异或运算”
- 33算法笔试模拟题精解之“小明的数学作业”
- 34算法笔试模拟题精解之“奇偶数列”
- 351.4 剪枝
- 361.5 尺取法
- 37算法笔试模拟题精解之“调整数组”
- 38算法笔试模拟题精解之“最优分组”
- 39算法笔试模拟题精解之“破译密码”
- 40二、数据结构
- 412.2 搜索
- 42算法笔试模拟题精解之“能量半径”
- 43算法笔试模拟题精解之“苹果收获程序”
- 44算法笔试模拟题精解之“恐怖的辐射”
- 45算法笔试模拟题精解之“树的拆分”
- 46算法笔试模拟题精解之“Password”
- 47算法笔试模拟题精解之“神奇数字在哪里”
- 48算法笔试模拟题精解之“神奇的棋子”
- 492.3 树
- 50算法笔试模拟题精解之“Codancer 的旅行”
- 51算法笔试模拟题精解之“Codancer 的求和”
- 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
- 532.4 线型
- 54算法笔试模拟题精解之“最活跃的数”
- 55算法笔试模拟题精解之“非递减序列”
- 56算法笔试模拟题精解之“Tom 跳方格”
- 57算法笔试模拟题精解之“复杂的字符串”
- 58算法笔试模拟题精解之“神秘消失”
- 59三、计算
- 60算法笔试模拟题精解之“简单题？
- 61算法笔试模拟题精解之“朋友一生一起走”
- 62算法笔试模拟题精解之“正三角塔”
- 63算法笔试模拟题精解之“组队难题”
- 64算法笔试模拟题精解之“2n 合体”
- 65算法笔试模拟题精解之“平行线”
- 66算法笔试模拟题精解之“叠叠高”
- 67算法笔试模拟题精解之“公平”
- 68算法笔试模拟题精解之“Tom 的手工课”
- 69算法笔试模拟题精解之“填数问题”
- 70算法笔试模拟题精解之“Jerry 的考验”
- 71算法笔试模拟题精解之“超车”
- 72算法笔试模拟题精解之“坏掉的时钟”
- 73算法笔试模拟题精解之“期末考试”
- 74算法笔试模拟题精解之“滑雪比赛”