遇到一个辐射问题，求解答。
一天，Codancer 突然发现自己身处一个奇怪的世界，他发现世界是一个 NM的矩形，在矩形的某些位置分布着一些恐怖的辐射源，每个辐射源都有相应的辐射等级，经过他的分析，这些辐射源总共有五个等级，分别命名为 A-E 级，A 级辐射等级为 15，B 级 14，C 级 12，D 级 7，E 级则没有辐射。奇怪的是，这些辐射源的辐射是沿着曼哈顿距离进行传播的且随曼哈顿距离递增辐射等级递减，并且，他会绕过其他辐射源，辐射源的等级不可叠加，这意味着如果某位置同时处于两个辐射源的影响范围，则他受到的辐射为辐射等级最高的那个。他知道当辐射等级小于等于 7 时，他受到的辐射将不会威胁到他的生命。因此，他想要知道，这个世界是否存在一个位置不会威胁到他的生命。每组数据的第一行和第二行分别为 N,M，接下来为 NM 的矩阵，'0' 代表空的位置，A-E 代表辐射源。（1<=N,M<=100）输出为 T 行，每行输出 "Yes" 或 "No"。
写回答
-
因为 N M 和最大辐射值都不大，所以可以直接模拟辐射扩散的实际情况，最后 判断是否有小于等于 7 的位置。首先把输入的字符串转化为二维数组，每个位置的值为初始的辐射值。同时还要记录辐射源的位置，因为辐射源的辐射值不会被更高辐射覆盖，即使辐射小于等于 7也不能生存。因为小于等于 7 的辐射就不会致命，而且辐射值最高的辐射源只有 15，所以最多只需要遍历 8 次，也就是说辐射值最高的辐射源 7 格之外就是安全得了。遍历时每一格的修改规则。如果是辐射源，则不修改。如果不是，修改规则如下。用下图的 a 位置举例，设 T(a) 为 a 位置辐射的当前值。需要对比T(a)T(b)-1T(c)-1 T(d)-1T(e)-1 的值，选其中最大的作为 a 位置的新值。减 1，是因为辐射扩散一次减少 1。最后遍历整个地图，判断是否有小于等于 7 的位置。 时间复杂度 O(9nm) 第一遍生成初始状态的数组，之后模拟辐射扩散 空间复杂度 O(2mn)
因此输入：2 3 ["0A0","00E"] 输出："No"
2021-12-23 18:48:20赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
