问题描述如下：
给定M行N列的矩阵，0表示空白，-1表示障碍，1表示目标点(存在多个目标点(。
对于每个空位，如果你想以最短的距离到达目标点，请标记第一步的方向。
如果启动，您应该将该点标记为2。如果从下开始，你应该把这一点标记为3。如果从左边开始，你应该把这一点标记为4。如果从右边开始，你应该把这一点标记为5。
方向的优先级是从大到小的上、下、左、右，也就是说，如果你能以最短的距离到达目标点，你就应该启动。
返回标记后的矩阵。0<m、 n<1000
我试图用python编写解决方案，但总是得到"TypeError:"NoneType"object is not iterable"。真的不知道为什么。如果你能指出问题所在，我将非常感谢你的帮助！
我的基本想法是，对于每个空单元格，使用BFS找到其最近的目标。然后，通过将这个空单元格指定为起点，将这个最近的目标指定为终点，我找到了第一步的方向。代码可能不那么简洁，感谢您的时间和精力！
class Solution:
"""
@param grid: the input matrix
@return: the new matrix
"""
grid = None
def shortestPath(self, grid):
# BFS
self.grid = grid.copy()
m = len(grid)
n = len(grid[0]) if m > 0 else 0
res = [[None] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if grid[i][j] not in [-1, 1]:
tarx, tary, step = self.bfs(i, j)
res[i][j] = self.search(i, j, tarx, tary)
else:
res[i][j] = grid[i][j]
return res
def search(self, i, j, tarx, tary):
dic = {0: 2, 1: 3, 2: 4, 3: 5}
dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
min_dist = float('inf')
direction = -1
for idx, d in enumerate(dirs):
x, y = i + d[0], j + d[1]
if x == tarx and y == tary:
return dic[idx]
if self.inside(x, y):
arr = [tarx, tary]
_, __, dist = self.bfs(x, y, arr)
if min_dist > dist:
min_dist = dist
direction = dic[idx]
return direction
def bfs(self, i, j, target = None):
m = len(self.grid)
n = len(self.grid[0]) if m > 0 else 0
visit = [[False] * n for _ in range(m)]
visit[i][j] = True
dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
qu = [(i, j, 0)]
while len(qu) > 0:
ti, tj, step = qu[0][0], qu[0][1], qu[0][2]
qu.pop()
for d in dirs:
x, y = ti + d[0], tj + d[1]
if self.inside(x, y) and not visit[x][y]:
if not target:
if self.grid[x][y] == 1:
return x, y, step + 1
else:
tarx, tary = target[0], target[1]
if x == tarx and y == tary:
return x, y, step + 1
visit[x][y] = True
qu.append((x, y, step + 1))
def inside(self, x, y):
if 0 <= x < len(self.grid) and 0 <= y < len(self.grid[0]) and self.grid[x][y] != -1:
return True
return False
if __name__ == '__main__':
testcase = [[1,0,0],[0,0,0]]
ans = Solution().shortestPath(testcase)
print(ans)
bfs不会从所有可能的执行路径返回三元组。如果您在没有找到解决方案的情况下完成了循环，那么您将退出底部并返回None。这会使您的开箱作业失败。
请参阅调试以备将来使用；我们希望你能做最初的问题诊断，而不仅仅是把一个未跟踪的程序扔给我们。