leetcode 1021 dfs 迷宫 最短

dfs求最短需要遍历所有路径，设置全局变量比较
leetcode global 关键字失效，使用self.
方法超时

global
nonlocal
https://blog.csdn.net/qq_42780289/article/details/89244761

讲条件从 for循环里拆出来

class Solution:
    def shortestPathBinaryMatrix(self, grid) -> int:
        self.minvalue= float('inf')

        def dfs(x, y, sum_val):
            direct = [(0, 1), (1, 0), (0, -1), (-1, 0), (1, -1), (-1, 1), (1, 1), (-1, -1)]
            #global minvalue
            if x<0 or y<0 or x>=len(grid) or y>=len(grid[0]):
                return 
            if grid[x][y]!=0:
                return 

            if x == len(grid) - 1 and y == len(grid[0]) - 1:
                self.minvalue = min(sum_val, self.minvalue)
                return

            grid[x][y] = 1
            for item in direct:

                    sum_val += 1

                    dfs(x + item[0], y + item[1], sum_val)

                    sum_val -= 1

            grid[x][y] = 0

        dfs(0, 0, 1)
        if self.minvalue == float('inf') :
            return -1
        else:
            return self.minvalue

最短路径 bfs
使用deque() .append() .popleft()
否则队列不会pop出元素。

 class Solution:
    def shortestPathBinaryMatrix(self, grid) -> int:

        direct = [(0, 1), (1, 0), (0, -1), (-1, 0), (1, -1), (-1, 1), (1, 1), (-1, -1)]

        queue=deque()
        queue.append([0,0])
        level=1
        if grid[0][0]==1 or grid[-1][-1]==1:
            return -1
        if len(grid)==1:
            return 1

        while queue:

            for _ in range(len(queue)):
                x,y=queue.popleft()



                for item in direct:
                    if x+item[0]==len(grid)-1 and y+item[1]==len(grid[0])-1:
                        return level+1
                    if 0<=x+item[0]<len(grid) and 0<=y+item[1]<len(grid[0]) and grid[x+item[0]][y+item[1]]==0:
                        queue.append([x+item[0],y+item[1]])
                        grid[x+item[0]][y+item[1]]=1


            level+=1
        return -1