<p>Given an <code>n x n</code> binary matrix <code>grid</code>, return <em>the length of the shortest <strong>clear path</strong> in the matrix</em>. If there is no clear path, return <code>-1</code>.</p>

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

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

<p>The <strong>length of a clear path</strong> is the number of visited cells of this path.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/18/example1_1.png" style="width: 500px; height: 234px;" />
<pre>
<strong>Input:</strong> grid = [[0,1],[1,0]]
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/18/example2_1.png" style="height: 216px; width: 500px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,0],[1,1,0],[1,1,0]]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0,0],[1,1,0],[1,1,0]]
<strong>Output:</strong> -1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>grid[i][j] is 0 or 1</code></li>
</ul>

// class Solution {
// public:
//     bool isValid(int i, int j, int n){
//         return i>=0 && j>=0 && i<n && j<n;
//     }
//     vector<pair<int,int>> direction = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
//     int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
//         int n = grid.size();
//         if(grid[0][0]||grid[n-1][n-1]){
//             return -1;
//         }
//         queue<pair<int,int>> q;
//         int length = 0; 
//         q.push({0,0});
//         vector<vector<bool>> visited(n, vector<bool> (n,false));
//         visited[0][0] = true; 
//         while(!q.empty()){ 
//             int sz = q.size();
//             length++;   
//             bool check = true;
//             for(int i=0;i<sz;i++){ 
//                 auto pair = q.front();
//                 q.pop(); 
//                 if(pair.first==n-1 && pair.second==n-1){
//                     return length;
//                 } 
//                 for(auto move: direction){
//                     int childX = move.first + pair.first;
//                     int childY = move.second + pair.second;
//                     if(isValid(childX,childY,n) ){ 
//                         if(!visited[childX][childY] && !grid[childX][childY]){
//                             check = false;
//                             q.push({childX,childY});
//                         }
//                         visited[childX][childY] = true;
//                     }
//                 }  
//             }
//             if(check){
//                 return -1;
//             } 
//         }
//         return length;
//     }
// };

class Solution {
public: 
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
           map<pair<int,int>,int>dist;
           int n =grid.size();
            for(int i(0);i<n;i++){
                 for(int j(0);j<n;j++){
                     dist[{i,j}]=INT_MAX;
                 }
            }
            if(grid[0][0]==1 || grid[n-1][n-1]==1){
                 return -1;
            }        
           dist[{0,0}]=1; 
           vector<vector<int>>dir={{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{-1,1},{1,-1}}; 
           vector<vector<int>>vis(n,vector<int>(n,-1));
           queue<pair<int,pair<int,int>>>pq;
           pq.push({1,{0,0}});
           vis[0][0]=1;  
           while(!pq.empty()){
                int x = (pq.front()).second.first;
                int y = (pq.front()).second.second;
                pq.pop(); 
                for(int i(0);i<8;i++){
                    int x_=x+dir[i][0];
                    int y_=y+dir[i][1];
                    if(x_>=0 && x_<=n-1 && y_>=0 && y_<=n-1){
                        if(vis[x_][y_]==-1 && grid[x_][y_]==0){ 
                            if(dist[{x,y}]+1<dist[{x_,y_}]){                    
                                dist[{x_,y_}]=dist[{x,y}]+1;
                                pq.push({dist[{x_,y_}],{x_,y_}});
                            } 
                            vis[x_][y_]=1;
                        }
                    }
                }

           }
           if(dist[{n-1,n-1}]==INT_MAX){
                return -1;
           }
        return dist[{n-1,n-1}];

    }
};
47594