在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：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)

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