在線編程介紹
阿里雲開發者社區在線編程產品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費在線刷題神器。題庫來自筆試模擬題、算法大賽模擬題等，界面整潔明瞭，操作簡單，為用戶營造專心答題的學習環境。點擊鏈接開始體驗：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)
看完之後是不是有了想法了呢，快來練練手吧>>查看題目
