python - 面试题 : find the direction of first step

Question

问题描述如下:

给定M行N列的矩阵，0代表空地，- 1代表障碍物，1代表目标点(有多个目标点)。

对于每一个空位，如果你想以最短的距离到达一个目标点，请标记第一步的方向。

起步时标为2，向下起步时标为3，向左起步时标为4，向右起步时标为5。

方向的优先顺序是上、下、左、右，从大到小，也就是说，如果你能到达距离上点或下点最短距离的目标点，你就应该启动。

标记后返回矩阵。 0< 米，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)

Answer 1

bfs不会从所有可能的执行路径返回三元组。如果在没有找到解决方案的情况下完成循环，则退出底部并返回 None .这会使您的拆包任务失败。

请查看 debug供您将来使用；我们希望您对问题进行初步诊断，而不仅仅是向我们倾倒未跟踪的程序。