<p>You are given an <code>m x n</code> matrix <code>maze</code> (<strong>0-indexed</strong>) with empty cells (represented as <code>&#39;.&#39;</code>) and walls (represented as <code>&#39;+&#39;</code>). You are also given the <code>entrance</code> of the maze, where <code>entrance = [entrance<sub>row</sub>, entrance<sub>col</sub>]</code> denotes the row and column of the cell you are initially standing at.</p>

<p>In one step, you can move one cell <strong>up</strong>, <strong>down</strong>, <strong>left</strong>, or <strong>right</strong>. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the <strong>nearest exit</strong> from the <code>entrance</code>. An <strong>exit</strong> is defined as an <strong>empty cell</strong> that is at the <strong>border</strong> of the <code>maze</code>. The <code>entrance</code> <strong>does not count</strong> as an exit.</p>

<p>Return <em>the <strong>number of steps</strong> in the shortest path from the </em><code>entrance</code><em> to the nearest exit, or </em><code>-1</code><em> if no such path exists</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/04/nearest1-grid.jpg" style="width: 333px; height: 253px;" />
<pre>
<strong>Input:</strong> maze = [[&quot;+&quot;,&quot;+&quot;,&quot;.&quot;,&quot;+&quot;],[&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;+&quot;],[&quot;+&quot;,&quot;+&quot;,&quot;+&quot;,&quot;.&quot;]], entrance = [1,2]
<strong>Output:</strong> 1
<strong>Explanation:</strong> There are 3 exits in this maze at [1,0], [0,2], and [2,3].
Initially, you are at the entrance cell [1,2].
- You can reach [1,0] by moving 2 steps left.
- You can reach [0,2] by moving 1 step up.
It is impossible to reach [2,3] from the entrance.
Thus, the nearest exit is [0,2], which is 1 step away.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/04/nearesr2-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> maze = [[&quot;+&quot;,&quot;+&quot;,&quot;+&quot;],[&quot;.&quot;,&quot;.&quot;,&quot;.&quot;],[&quot;+&quot;,&quot;+&quot;,&quot;+&quot;]], entrance = [1,0]
<strong>Output:</strong> 2
<strong>Explanation:</strong> There is 1 exit in this maze at [1,2].
[1,0] does not count as an exit since it is the entrance cell.
Initially, you are at the entrance cell [1,0].
- You can reach [1,2] by moving 2 steps right.
Thus, the nearest exit is [1,2], which is 2 steps away.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/04/nearest3-grid.jpg" style="width: 173px; height: 93px;" />
<pre>
<strong>Input:</strong> maze = [[&quot;.&quot;,&quot;+&quot;]], entrance = [0,0]
<strong>Output:</strong> -1
<strong>Explanation:</strong> There are no exits in this maze.
</pre>

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

<ul>
	<li><code>maze.length == m</code></li>
	<li><code>maze[i].length == n</code></li>
	<li><code>1 &lt;= m, n &lt;= 100</code></li>
	<li><code>maze[i][j]</code> is either <code>&#39;.&#39;</code> or <code>&#39;+&#39;</code>.</li>
	<li><code>entrance.length == 2</code></li>
	<li><code>0 &lt;= entrance<sub>row</sub> &lt; m</code></li>
	<li><code>0 &lt;= entrance<sub>col</sub> &lt; n</code></li>
	<li><code>entrance</code> will always be an empty cell.</li>
</ul>

class Solution {
public:

    bool BorderCell( pair< int, int > cell , vector<vector< char>> &maze) {

        int r = cell.first;

        int c = cell.second;

        return  r == 0 || r ==  maze.size() - 1 || c == 0 || c == maze[0].size() - 1;
    };

    vector< vector< int >> directions = { {0 , 1} , {0 , -1} , {-1 , 0} , {1 , 0} };

    bool NoExit( vector<vector<char> > &maze , vector<int> &entrance ) {

        // ROW 0 

        // ROW maze.size() - 1

        for( int c = 0; c < maze[0].size(); c++ ) {

            // cout << 0 << " " << c << endl;
            // cout << maze.size() - 1 << " " << c << endl;

            if( maze[ 0 ][ c ] == '.' && ( to_string( 0 ) + "-" + to_string( c) != to_string( entrance[0] ) + "-" + to_string( entrance[1])) ) {

                return true;
            }

            if( maze[ maze.size() - 1 ][ c ] == '.' && ( to_string( maze.size() - 1 ) + "-" + to_string( c ) != to_string( entrance[0] ) + "-" + to_string( entrance[1])) ) {

                return true;
            }
        }


        // COLUMN 0 

        // COLUMN maze[0].size() - 1

        for( int r = 0; r < maze.size() ; r++ ) {

            // cout << r << " " << 0 << endl;

            // cout << r << " " << maze[0].size() - 1 << endl;

            if( maze[ r ][ 0 ] == '.' && ( to_string( r ) + "-" + to_string( 0 ) != to_string( entrance[0] ) + "-" + to_string( entrance[1]) ) ) {

                return true;
            }

            if( maze[ r ][ maze[0].size() - 1 ] == '.' && ( to_string( r ) + "-" + to_string( maze[0].size() - 1) != to_string( entrance[0] ) + "-" + to_string( entrance[1])) ){

                return true;
            }
        }


        return false;
};
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {

        queue< pair< int, int > > myqueue;

        unordered_set< string > AlreadyTraversed;

        myqueue.push( make_pair( entrance[0] , entrance[1] ) );

        int steps = -1;

        bool border_found = false;

        while( myqueue.size() != 0 ) {

            // THE FOLLOWING WILL BE ALL POSSIBLE PATHS THAT CAN BE TRAVELLED IN 1 STEP ( WE ARE TRAVERSING LAYER BY LAYER)
            steps++;

            int size = myqueue.size();

            cout << "steps: " << steps << endl;

            while( size-- ) {

                pair< int, int > curr = myqueue.front();

                cout << "current cell: " << curr.first << " " << curr.second << endl;

                myqueue.pop();

                // BORDER CELL

                if( BorderCell( curr , maze ) && ( to_string( curr.first ) + "-" + to_string( curr.second) != to_string( entrance[0] ) + "-" + to_string( entrance[1]) ) ) {

                    cout << "reached the border cell: " << curr.first << " " << curr.second << endl;

                    border_found = true;

                    return steps;

                    break;
                }

                else{

                    cout << "not a border cell: " << curr.first << " " << curr.second << endl;
                }

                // PUSH THE CURRENT CELL IN ALREADY TRAVERSED

                AlreadyTraversed.insert( to_string( curr.first ) + "-" + to_string( curr.second ));

                // PUSH ALL 4 OF ITS TRAVERSABLE NODES IN THE QUEUE

                for( vector< int > &direction : directions ) {

                    int r = curr.first + direction[ 0 ];

                    int c = curr.second + direction[ 1 ];

                    // VALID CELL TO TRAVERSE

                    if( r >= 0 && r < maze.size() && c >= 0 && c < maze[0].size() && maze[ r ][ c ] == '.' && AlreadyTraversed.find( to_string( r ) + "-" + to_string( c )) == AlreadyTraversed.end() ) {

                        myqueue.push( make_pair( r , c) );

                        AlreadyTraversed.insert( to_string( r ) + "-" + to_string( c ));
                    }
                }
            }


            if( border_found ) {

                break;
            }
        }

        if( border_found ) {

            return steps;
        }

        else{

            return -1;
        }

        return steps;

    }
};
46378