<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 {
int ans =0;
private:
    void bfs(vector<vector<int>>& grid)
    {
        int n = grid.size();
        vector<vector<int>> visited(n, vector<int>(n, 0));
        queue<vector<int>> q;
        q.push({0,0,1});
        visited[0][0]=1;
        ans++;
        int added =0;
        int found =0;
        while(!q.empty()&&!found)
        {
            auto vec = q.front();
            int i = vec[0];
            int j = vec[1];
            ans = vec[2];
            q.pop();
            
            if(i+1<n&&j+1<n&&grid[i+1][j+1]==0&&!visited[i+1][j+1])
            {
              q.push({i+1,j+1,ans+1});
              added =1;
              visited[i+1][j+1] =1;
              if(i+1==n-1&&j+1==n-1)
              {
                 found =1;
                 ans = ans +1;
              }
            }
            if(i+1<n&&grid[i+1][j]==0&&!visited[i+1][j])
            {
              q.push({i+1,j,ans+1});
              added = 1;
              visited[i+1][j] = 1;
              if(i+1==n-1&&j==n-1)
              {
                 found =1;
                 ans = ans +1;
              }
              
            }
            if(j+1<n&&grid[i][j+1]==0&&!visited[i][j+1])
            {
              q.push({i,j+1,ans+1});
              added = 1;
              visited[i][j+1] = 1;
              if(i==n-1&&j+1==n-1)
              {
                 found =1;
                 ans = ans +1;
              }
            }
            if(i-1>=0&&grid[i-1][j]==0&&!visited[i-1][j])
            {
                q.push({i-1,j,ans+1});
                added = 1;
                visited[i-1][j] = 1;
              if(i-1==n-1&&j==n-1)
              {
                 found =1;
                 ans = ans +1;
              }
            }
            if(i-1>=0&&j-1>=0&&grid[i-1][j-1]==0&&!visited[i-1][j-1])
            {
                q.push({i-1,j-1,ans+1});
                added =1 ;
                visited[i-1][j-1] = 1;
                if(i-1==n-1&&j-1==n-1)
                {
                  found =1;
                  ans = ans +1;
                }
            }
            if(j-1>=0&&grid[i][j-1]==0&&!visited[i][j-1])
            {
                q.push({i,j-1,ans+1});
                added = 1;
                visited[i][j-1] = 1;
                if(i==n-1&&j-1==n-1)
                {
                  found =1;
                  ans = ans +1;
                }
            }
            if(i+1<n&&j-1>=0&&grid[i+1][j-1]==0&&!visited[i+1][j-1])
            {
                q.push({i+1,j-1,ans+1});
                added = 1;
                visited[i+1][j-1] = 1;
                if(i+1==n-1&&j-1==n-1)
                {
                  found =1;
                  ans = ans +1;
                }
            }
            if(j+1<n&&i-1>=0&&grid[i-1][j+1]==0&&!visited[i-1][j+1])
            {
                q.push({i-1,j+1,ans+1});
                added = 1;
                visited[i-1][j+1] = 1;
                if(i-1==n-1&&j+1==n-1)
                {
                  found =1;
                  ans = ans +1;
                }
            }
            // if(q.empty())
            // {
            //     if(i!=n-1||j!=n-1)
            //       ans =-2;
            // }
        }
        if(found ==0)
          ans = -1;
    }
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if(grid[0][0]!=0)
          return -1;
        int n = grid.size();
        if(grid[n-1][n-1]!=0)
          return -1;
        if(n==1)
          return 1;
        int j =0;
        int i =0;
        if(i+1<n&&j+1<n&&grid[i][j+1]==1&&grid[i+1][j+1]==1&&grid[i+1][j]==1)
           return -1;
        i = n-1;
        j = n-1;
        if(i-1>=0&&j-1>=0&&grid[i-1][j]==1&&grid[i-1][j-1]==1&&grid[i][j-1]==1)
          return -1;
        bfs(grid);
        return ans;

    }
};
// 0  0 0
// 1  0 0
// 1  1 0

// 0 - 0 +1
// 0 - 0 0 +1
// 0 - 0 +0
// 0 - 0 +1

// 0 0 0 0
// 0 0 1 0
// 1 0 1 1
// 1 1 1 0 
//[[0,0,0,0],[0,0,1,0],[1,0,1,1],[1,1,1,0]]
// 0 - 0 0 0
// 0 - 0 0 0  
// 0 - 0 0 0 
// 0 - 0 0  + 0
// 0 - 0 0 0
// 0 - 0 0 +0
// 0 - 0  +0
// 0 - 0 
// 0 - 0
// 0 -  +0

// 0 0 0 0 0
// 0 1 1 1 1
// 0 0 0 0 0
// 0 0 0 0 0
// 0 1 1 1 0

// [[0,0,0,0,0],[0,1,1,1,1],[0,0,0,0,0],[0,0,0,0,0],[0,1,1,1,0]]
40630