Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:


	All the visited cells of the path are 0.
	All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).


The length of a clear path is the number of visited cells of this path.

&nbsp;
Example 1:

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


Example 2:

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


Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1


&nbsp;
Constraints:


	n == grid.length
	n == grid[i].length
	1 &lt;= n &lt;= 100
	grid[i][j] is 0 or 1


'''
from collections import deque
class Solution:
	def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
		L=len(grid)
		def generate_next_state(i,j):
			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)]
		def valid_state(states):
			res=[]
			for (i,j) in states:
				if i>L-1:continue
				if i<0:continue
				if j<0:continue
				if j>L-1:continue
				if grid[i][j]==0:
					res.append((i,j))
			return res
		queue=deque([(0,0)])
		res=1
		while queue:
			for _ in range(len(queue)):
				i,j=queue.popleft()
				val=grid[i][j]
				grid[i][j]=1
				if not val:
					if i==L-1 and j==L-1:
						return res

					next_state=valid_state(generate_next_state(i,j))
					for (ki,kj) in next_state:
						queue.append((ki,kj))
			res+=1
		return -1
                
        
        
    
'''
class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        
        boolean [][] visited = new boolean [m][n];
        
        int [] up = {0, 0, 1, -1, 1, 1, -1, -1};
        int [] down = {-1, 1, 0, 0, -1, 1, -1, 1};
        
        /*
        if top-left is 1 or bottom-right is 1
        we will return -1
        */
        if(grid[0][0] == 1 || grid[m-1][n-1] == 1)
            return -1;
        
        ArrayDeque<int []> q = new ArrayDeque<>();
        /*
        we will add top-left to the deque
        ans steps as 1
        */
        q.add(new int[]{0,0,1});        
        
        while(q.size() > 0){
            int [] tmp = q.removeFirst();
            int x = tmp[0];
            int y = tmp[1];
            int steps = tmp[2];
            visited[x][y] = true;
            
            if(x == m-1 && y == n-1)
                return steps;
            
            for(int i = 0; i < 8; i++){
                int x_new = x + up[i];
                int y_new = y + down[i];
                /*
                we will traverse level wise using bfs
                and those which can be directly reach via
                current level will be considered as the same
                level and we will return the level of 
                bottom-right as result
                */
                if(x_new >= 0 && x_new < m && y_new >= 0 && y_new < n){
                    if(visited[x_new][y_new] == false && grid[x_new][y_new] == 0){
                        q.add(new int[]{x_new,y_new,steps+1});
                        visited[x_new][y_new] = true;
                    }
                }
            }
        }
        
        return -1;
    }
}
class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int m = grid.size(),n = grid[0].size();
        if(grid[0][0]!=0 || grid[m-1][n-1]!=0) return -1;
        vector<vector<int>> dist(m,vector<int>(n,INT_MAX));
        int ans = INT_MAX;
        queue<pair<int,int>> q;
        dist[0][0]=1;
        q.push({0,0});
        
        int dir[8][2] = {{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};
        while(!q.empty()){
            auto curr = q.front();
            q.pop();
            for(int i = 0;i<8;i++){
                int newi = curr.first + dir[i][0];
                int newj = curr.second + dir[i][1];
                if(newi>=0 && newi<m && newj>=0 && newj<n && grid[newi][newj]==0){
                    if(dist[newi][newj]>dist[curr.first][curr.second]+1){
                        dist[newi][newj] = dist[curr.first][curr.second]+1;
                        q.push({newi,newj});
                    }
                }
            }
        }
            
        return dist[m-1][n-1]==INT_MAX?-1:dist[m-1][n-1]; 
    }
};
/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestPathBinaryMatrix = function(grid) {
    const n = grid.length
    const directions = [
        [-1, 0], [-1, 1], [0, 1], [1, 1],
        [1, 0], [1, -1], [0, -1], [-1, -1]
    ]
    const visited = []
    const distance = []
    const predecessor = []
    const queue = []

    for (let i = 0; i < n; i++ ) {
        visited.push(Array.from({length: n}, (v, i) => false))
        distance.push(Array.from({length: n}, (v, i) => 9999))
        predecessor.push(Array.from({length: n}, (v, i) => null))
    }

    const startIndex = [0, 0]
    if(grid[startIndex[0]][startIndex[1]] !== 0) {
        return -1
    }

    queue.push(startIndex)
    distance[startIndex[0]][startIndex[1]] = 1

    while(queue.length > 0) {
        const current = queue.shift()
        visited[current[0]][current[1]] = true

        if (current[0] === n-1 && current[1] === n-1) {
            break
        }

        directions.forEach(dir => {
            const x = current[0] + dir[0]
            const y = current[1] + dir[1]

            if (x < 0 || y < 0 || x >= n || y >= n) {
                return
            }

            if (
                grid[x][y] === 0 &&
                visited[x][y] === false &&
                distance[x][y] > distance[current[0]][current[1]] + 1
            ) {
                distance[x][y] = distance[current[0]][current[1]] + 1
                predecessor[x][y] = current
                queue.push([x, y])
            }
        })
    }

    console.log(distance)
    console.log(visited)
    console.log(predecessor)

    return distance[n-1][n-1] >= 999 ?
        -1 : distance[n-1][n-1]
};
Shortest Path in Binary Matrix