<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
{
private:
    using Position = struct
    {
        int x, y;
    };
    using VisitingMap = std::vector<std::vector<bool>>;
    using Map = std::vector<std::vector<char>>;
    using QueueItem = std::pair<Position, int>;
    using Queue = std::queue<QueueItem>;

    inline int min(int a, int b)
    {
        return a < b ? a : b;
    }

    std::vector<Position> get_directions(const Position &position, std::size_t rows, std::size_t columns)
    {
        std::vector<Position> directions;

        if (position.y > 0)
            directions.push_back({position.x, position.y - 1});

        if (position.x > 0)
            directions.push_back({position.x - 1, position.y});

        if (position.y < rows - 1)
            directions.push_back({position.x, position.y + 1});

        if (position.x < columns - 1)
            directions.push_back({position.x + 1, position.y});

        return directions;
    }

    void queue_push(Queue &queue, VisitingMap &visiting_map, const QueueItem &item)
    {
        queue.push(item);
        visiting_map[item.first.y][item.first.x] = true;
    }

    bool is_entrance(const std::vector<int> &entrance, int x, int y)
    {
        return x == entrance[1] && y == entrance[0];
    }

public:
    int nearestExit(Map &maze, std::vector<int> &entrance)
    {
        uint8_t rows = maze.size(),
                columns = maze[0].size();
        VisitingMap visiting_map(rows, std::vector(columns, false));
        Queue queue;

        for (uint8_t i = 0; i < rows; ++i)
            if (maze[i][0] == '.' && !is_entrance(entrance, 0, i))
                queue_push(queue, visiting_map, {{0, i}, 0});
        for (uint8_t i = 0; i < rows; ++i)
            if (maze[i][columns - 1] == '.' && !is_entrance(entrance, columns - 1, i))
                queue_push(queue, visiting_map, {{columns - 1, i}, 0});

        for (uint8_t i = 0; i < columns; ++i)
            if (maze[0][i] == '.' && !is_entrance(entrance, i, 0))
                queue_push(queue, visiting_map, {{i, 0}, 0});
        for (uint8_t i = 0; i < columns; ++i)
            if (maze[rows - 1][i] == '.' && !is_entrance(entrance, i, rows - 1))
                queue_push(queue, visiting_map, {{i, rows - 1}, 0});

        if (queue.empty())
            return -1;

        auto curr = queue.front();
        queue.pop();

        while (true)
        {
            std::cout << "Visiting: " << curr.first.x << ", " << curr.first.y << "\n";
            std::vector<Position> directions = get_directions(curr.first, rows, columns);

            for (const auto &direction : directions)
            {
                if (maze[direction.y][direction.x] != '+' && !visiting_map[direction.y][direction.x])
                {
                    if (is_entrance(entrance, direction.x, direction.y))
                        return curr.second + 1;
                    else
                        queue_push(queue, visiting_map, {direction, curr.second + 1});
                }
            }

            if (queue.empty())
                return -1;

            curr = queue.front();
            queue.pop();
        }
    }
};
51259