# class Solution:
#     def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
#         if grid[0][0]==1:
#             return -1
#         result=[]
#         width=len(grid[0])
#         height=len(grid)
#         directions=[1,0,-1]
#         def findroute(x,y,length):
#             if x==height-1 and y==width-1:
#                 result.append(length+1)
#             for i in directions:
#                 for j in directions:
#                     #print(x+i,y+j)
#                     if x+i>=0 and x+i<height and y+j>=0 and y+j<width:
#                         if grid[x+i][y+j]==0:
#                             grid[x+i][y+j]=1
#                             findroute(x+i,y+j,length+1)
#                             grid[x+i][y+j]=0
                            
#         grid[0][0]=1
#         findroute(0,0,0)
#         if len(result)==0:
#             return -1
#         return min(result)

#回溯算法时间复杂度过高不可用

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0]==1:
            return -1
        queue=[[0,0]]
        step=1
        directions=[1,0,-1]
        width=len(grid[0])
        height=len(grid)
        if width==1 and height==1:
         return 1
        widthw=1
        nextw=0
        grid[0][0]=1
        while len(queue)!=0:
            #print(queue)
            curr=queue.pop(0)
            x=curr[0]
            y=curr[1]
            for i in directions:
                for j in directions:
                    if x+i>=0 and x+i<height and y+j>=0 and y+j<width and grid[x+i][y+j]==0:
                        if x+i==height-1 and y+j==width-1:
                            return step+1
                        grid[x+i][y+j]=1
                        queue.append([x+i,y+j])
                        nextw+=1
            widthw-=1
            if widthw==0:
                widthw=nextw
                nextw=0
                step+=1
        return -1

'''
执行用时：
824 ms
, 在所有 Python3 提交中击败了
26.72%
的用户
内存消耗：
13.9 MB
, 在所有 Python3 提交中击败了
34.59%
的用户
'''