題目描述

在2XXX年，人們發現了一塊火星地區，這里看起來很適合建設新家園。但問題是，我們不能一次性將這片地區的空氣變得適合人類居住，得分步驟來。
把這片火星地區想象成一個巨大的棋盤。棋盤上的每個格子，都有三種可能的狀態：

• YES：這片區域的空氣已經被改造好了，人類可以在這里生活。
• NO：這片區域還未改造，但未來是可以被改造的。
• NA：這是個死區，我們不能對其進行改造也不能穿過它。
  好消息是，已經改造好的區域（YES）每當大陽日到來，它就會自動幫我們改造與其相鄰的四個方向（上下左右）的NO區域，使其變成YES。

目標

• 告訴我們，這整片待改造的火星地區是否能完全變成適合人類居住的地方。如果可以，需要多少個大陽日來完成？如果不可能，就直接“不可能”。

輸入

• 一個代表火星地區的棋盤，其中每個格子是：YES、NO、NA。

輸出

• 天數

代碼實現

# 檢測是否已被全部開拓
def check(mat, m): # m-行數for i in range(m):if 'NO' in mat[i]:return Falsereturn True    
# i,j 為每次開拓的節點， 獲取(i, j)周圍可以開拓的節點的集合
def getList(mat, i, j, m, n):path = [[-1, 0], [1, 0], [0, -1], [0, 1]]res = []for p in path:next_i, next_j = p[0] + i, p[1] + jif 0<= next_i < m and 0<= next_j < n:if mat[i][j] == 'YES' and mat[next_i][next_j] == 'N0':res.append([next_i, next_j])elif mat[i][j] == 'NO' and mat[next_i][next_j] == 'YES':res.append([i, j])return resdef solve(mat):m, n = len(mat), len(mat[0])if m == 0 or n == 0:return 0# NA檢測for i in range(m):if 'NA' in mat[i]:return -1    times = 0while check(mat, m) == False:# 渲染arr = []for i in range(m):for j in range(n):res = getList(mat, i, j, m, n)if len(res) > 0:for data in res:arr.append(data)if len(arr) > 0:for data in arr:mat[data[0]][data[1]] = 'YES'                times += 1         return timesmat = [['NO', 'NO', 'YES', 'NO', 'NO'],['YES', 'NO', 'NO', 'NO', 'NO'],['YES', 'NO', 'NO', 'NO', 'NO'],
]
print(solve(mat)
)