In an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, ..., C_k such that:

• Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner)
• C_1 is at location (0, 0) (ie. has value grid[0][0])
• C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1])
• If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0).

Return the length of the shortest such clear path from top-left to bottom-right.  If such a path does not exist, return -1.

 

Example 1:

Input: [[0,1],[1,0]]
Output: 2

Example 2:

Input: [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

 

Note:

1. 1 <= grid.length == grid[0].length <= 100
2. grid[i][j] is 0 or 1

思路：BFS

class Solution(object):
    def shortestPathBinaryMatrix(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n,m=len(grid),len(grid[0])
        if grid[0][0]==1 or grid[n-1][m-1]==1: return -1
        vis=set([(n-1,m-1)])
        q,qq=[(n-1,m-1)],[]
        step=0
        dirs=[[1,0],[-1,0],[0,1],[0,-1],
              [1,1],[-1,1],[1,-1],[-1,-1]]
        while q:
            while q:
                i,j=q.pop()
                for di,dj in dirs:
                    ii,jj=i+di,j+dj
                    if 0<=ii<n and 0<=jj<m and grid[ii][jj]==0:
                        if (ii,jj) in vis: continue
                        vis.add((ii,jj))
                        qq.append((ii,jj))
                        if ii==0 and jj==0: return step+2
            step+=1
            q,qq=qq,q
        return -1