1
"""
2
from collections import deque
3
class Solution:
4
        def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
5
                L=len(grid)
6
                def generate_next_state(i,j):
7
                        return [(i+1,j),(i-1,j),(i,j+1),(i,j-1),(i+1,j-1),(i+1,j+1),(i-1,j-1),(i-1,j+1)]
8
                def valid_state(states):
9
                        res=[]
10
                        for (i,j) in states:
11
                                if i>L-1:continue
12
                                if i<0:continue
13
                                if j<0:continue
14
                                if j>L-1:continue
15
                                if grid[i][j]==0:
16
                                        res.append((i,j))
17
                        return res
18
                queue=deque([(0,0)])
19
                res=1
20
                while queue:
21
                        for _ in range(len(queue)):
22
                                i,j=queue.popleft()
23
                                val=grid[i][j]
24
                                grid[i][j]=1
25
                                if not val:
26
                                        if i==L-1 and j==L-1:
27
                                                return res
28

29
                                        next_state=valid_state(generate_next_state(i,j))
30
                                        for (ki,kj) in next_state:
31
                                                queue.append((ki,kj))
32
                        res+=1
33
                return -1
34

35

36

37

38
"""