题目描述

在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)
)