题目描述

https://leetcode-cn.com/problemset/all/?search=505

BFS

从起点出发，携带方向属性，做BFS，一般这种最短路径，考虑用BFS比DFS方便

python 代码

    def shortestDistance_maze(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        Q = collections.deque()
        directions = [[1,0],[0,1],[-1,0],[0,-1]]
        row = len(maze)
        column = len(maze)
        visited = []
        distance = [[0 for _ in range(column)] for _ in range(row)]
        def BFS(i,j, fx_list):
            for fx in fx_list:
                Q.append([i,j, fx, 0])
            while Q:
                tmp = Q.popleft()
                x = tmp[0]
                y = tmp[1]
                fx = tmp[2]
                layer = tmp[3]
                distance[x][y] = layer
                visited.append([x,y])
                if x+fx[0] not in range(row) or y+fx[1] not in range(column) or maze[x+fx[0]][y+fx[1]] == 1:
                    # 前进方向碰壁，可重新选择方向
                    count = 0
                    for direction in directions:
                        m = x+direction[0]
                        n = y+direction[1]
                        if m in range(row) and n in range(column) and maze[m][n]==0 and [m,n] not in visited:
                            Q.append([m, n, direction, layer+1])
                            count+=1
                    if count == 0 and x  == destination[0] and y == destination[1]:
                        print(distance)
                        return distance[x][y]
                # 未触碰到边缘
                elif maze[x+fx[0]][y+fx[1]] == 0:
                    Q.append([x+fx[0], y+fx[1], fx, layer+1])
            print(distance)
            return -1
        list1 = []
        for direction in directions:
            x = start[0]+direction[0]
            y = start[1]+direction[1]
            if x in range(row) and y in range(column) and maze[x][y] == 0:
                list1.append(direction)
        return BFS(start[0],start[1],list1)