<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>

#define MAX_NODE 101

class Solution {
public:
    
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        queue <vector<int>> qLocationQueue;        
        vector <vector<int>> vtInQueue(MAX_NODE, vector<int> (MAX_NODE));        

        int nRow = 0;
        int nCol = 0;         
        vector <int> vtCurNodeLocation;

        int nMaxN = grid.size(); 
        int nDestRowAndCol = nMaxN - 1;

        if (grid[nRow][nCol] == 1 || grid[nDestRowAndCol][nDestRowAndCol] == 1)
            return -1;      

        if ( nMaxN == 1 )
            return 1;
        
    
        
        vtCurNodeLocation.push_back(nRow);
        vtCurNodeLocation.push_back(nCol);

        qLocationQueue.push(vtCurNodeLocation);
        vtInQueue[0][0] = 1;

        while (qLocationQueue.size())
        {
            vtCurNodeLocation = qLocationQueue.front();
            nRow = vtCurNodeLocation[0];
            nCol = vtCurNodeLocation[1];
            qLocationQueue.pop();     

            for ( int nAddX = -1; nAddX < 2; nAddX++)
            {
                for (int nAddY = -1; nAddY < 2; nAddY++)
                {
                    
                    if ( nAddX == 0 && nAddY == 0)
                        continue;

                    int nCurX = nRow + nAddX;
                    int nCurY = nCol + nAddY;
                
                    if ( nCurX < 0 || nCurY < 0)
                        continue;                

                    if (nCurX == nMaxN || nCurY == nMaxN)
                        continue;                                            
                    
                    if (grid[nCurX][nCurY] == 1)
                        continue;

                    if (vtInQueue[nCurX][nCurY])
                        continue;                           
                    
                    vtCurNodeLocation[0] = nCurX;
                    vtCurNodeLocation[1] = nCurY;

                    qLocationQueue.push(vtCurNodeLocation);
                    vtInQueue[nCurX][nCurY] = vtInQueue[nRow][nCol] + 1;
                    
                }
            }
        }

        int nRes = vtInQueue[nDestRowAndCol][nDestRowAndCol];


        if ( nRes == 0) 
            return -1;

        return nRes;            
    }
};
39856