線上程式設計介紹
阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：
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)
看完之後是不是有了想法了呢，快來練練手吧>>
檢視題目