<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:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        vector<int> vertic_directions = {-1, 1, 0, 0};
        vector<int> horizo_directions = {0, 0, -1, 1};        
        vector<int> e(entrance);
        vector<int>::iterator itr;
        vector<int> answers;
        unordered_map<int, vector<int>> spot_track_keeper;

        bool isEntrance = true;//both BFS and DFS
        int ans = 0;//both BFS and DFS

        queue<vector<int>> BFS_track;//stack of BFS nodes
        vector<int> curNode(entrance);//assign first node
        BFS_track.push({curNode[0], curNode[1], 0});//BFS insert the first node
        vector<int> temp;
        int row;
        int col;
        int curSteps;
        

        for (auto i : maze){
            cout << "[";
            int n = i.size();
            for (int j = 0; j < n; j++){
                cout << i[j];
            }
            cout << "]" << endl;
        }
        cout << " -------------------" << endl;


        while(!BFS_track.empty()){
            if (isEntrance){
                isEntrance = false;
                temp = BFS_track.front();
                row = temp[0];
                col = temp[1];
                curSteps = temp[2];
                maze[row][col] = '+';
                BFS_track.pop();
                //confirm limits are within bounds then check if node is a wall and if not then add it to queue
                if (row+1 >= 0 && row+1 < maze.size()){
                    if (maze[row+1][col] != '+') {
                        maze[row+1][col] = '+';
                        BFS_track.push({row+1,col,curSteps + 1});
                    }
                }
                if (row-1 >= 0 && row-1 < maze.size()){
                    if (maze[row-1][col] != '+') {
                        maze[row-1][col] = '+';
                        BFS_track.push({row-1,col,curSteps + 1});
                    }
                }
                if (col+1 >= 0 && col+1 < maze[0].size()){
                    if (maze[row][col+1] != '+') {
                        maze[row][col+1] = '+';
                        BFS_track.push({row,col+1,curSteps + 1});
                    }
                }
                if (col-1 >= 0 && col-1 < maze[0].size()){
                    if (maze[row][col-1] != '+') {
                        maze[row][col-1] = '+';
                        BFS_track.push({row,col-1,curSteps + 1});
                    }
                }
            } else {
                int n = BFS_track.size();
                for (int i = 0; i < n; i++){
                    temp = BFS_track.front();
                    row = temp[0];
                    col = temp[1];
                    curSteps = temp[2];
                    maze[row][col] = '+';
                    BFS_track.pop();
                    //check if exit is reached
                    if (row == 0 || row == maze.size() -1 || col == 0 || col == maze[0].size() - 1){
                        if (ans == 0) {
                            ans = curSteps;
                        } else {
                            ans = min(ans, curSteps);
                        }
                    }
                    if (row+1 >= 0 && row+1 < maze.size()){
                        if (maze[row+1][col] != '+') {
                            maze[row+1][col] = '+';
                            BFS_track.push({row+1,col,curSteps + 1});
                        }
                    }
                    if (row-1 >= 0 && row-1 < maze.size()){
                        if (maze[row-1][col] != '+') {
                            maze[row-1][col] = '+';
                            BFS_track.push({row-1,col,curSteps + 1});
                        }
                    }
                    if (col+1 >= 0 && col+1 < maze[0].size()){
                        if (maze[row][col+1] != '+') {
                            maze[row][col+1] = '+';
                            BFS_track.push({row,col+1,curSteps + 1});
                        }
                    }
                    if (col-1 >= 0 && col-1 < maze[0].size()){
                        if (maze[row][col-1] != '+') {
                            maze[row][col-1] = '+';
                            BFS_track.push({row,col-1,curSteps + 1});
                        }
                    }
                }
            }
        }

        //DFS(maze, entrance[0], entrance[1], curSteps, ans, isEntrance, answers);

        for (auto i : maze){
            cout << "[";
            int n = i.size();
            for (int j = 0; j < n; j++){
                cout << i[j];
            }
            cout << "]" << endl;
        }

        return ans==0?-1:ans;
    }

    void DFS(vector<vector<char>>& maze, int row, int col, int& curSteps, int& ans, bool& isEntrance, vector<int>& answers){
        if (row < 0 || row >= maze.size() || col < 0 || col >= maze[0].size()){
            return;
        }
        if (maze[row][col] == '+'){
            return;
        }
        if ((row == 0 || row == maze.size() - 1 || col == 0 || col == maze[0].size() - 1) && (maze[row][col] != '+') && (!isEntrance)) {
            //answers.push_back(curSteps);
            cout << "curSteps && limit reached: " << curSteps << " row: " << row << " col: " << col << endl;
            
            if (ans == 0){
                ans = curSteps;
            } else {
                ans = min(ans, curSteps);
            }
            curSteps = 0;
            return;
        }
        curSteps++;
        cout << "curSteps no limit reached: " << curSteps << " row: " << row << " col: " << col << endl;
        isEntrance = false;
        maze[row][col] = '+';
        DFS(maze, row+1, col, curSteps, ans, isEntrance, answers);//down
        DFS(maze, row, col+1, curSteps, ans, isEntrance, answers);//right
        DFS(maze, row-1, col, curSteps, ans, isEntrance, answers);//up
        DFS(maze, row, col-1, curSteps, ans, isEntrance, answers);//left
        

    }
};
57028