<p>You are given a <strong>0-indexed</strong> 2D matrix <code>grid</code> of size <code>n x n</code>, where <code>(r, c)</code> represents:</p>

<ul>
	<li>A cell containing a thief if <code>grid[r][c] = 1</code></li>
	<li>An empty cell if <code>grid[r][c] = 0</code></li>
</ul>

<p>You are initially positioned at cell <code>(0, 0)</code>. In one move, you can move to any adjacent cell in the grid, including cells containing thieves.</p>

<p>The <strong>safeness factor</strong> of a path on the grid is defined as the <strong>minimum</strong> manhattan distance from any cell in the path to any thief in the grid.</p>

<p>Return <em>the <strong>maximum safeness factor</strong> of all paths leading to cell </em><code>(n - 1, n - 1)</code><em>.</em></p>

<p>An <strong>adjacent</strong> cell of cell <code>(r, c)</code>, is one of the cells <code>(r, c + 1)</code>, <code>(r, c - 1)</code>, <code>(r + 1, c)</code> and <code>(r - 1, c)</code> if it exists.</p>

<p>The <strong>Manhattan distance</strong> between two cells <code>(a, b)</code> and <code>(x, y)</code> is equal to <code>|a - x| + |b - y|</code>, where <code>|val|</code> denotes the absolute value of val.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/07/02/example1.png" style="width: 362px; height: 242px;" />
<pre>
<strong>Input:</strong> grid = [[1,0,0],[0,0,0],[0,0,1]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> All paths from (0, 0) to (n - 1, n - 1) go through the thieves in cells (0, 0) and (n - 1, n - 1).
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/07/02/example2.png" style="width: 362px; height: 242px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,1],[0,0,0],[0,0,0]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The path depicted in the picture above has a safeness factor of 2 since:
- The closest cell of the path to the thief at cell (0, 2) is cell (0, 0). The distance between them is | 0 - 0 | + | 0 - 2 | = 2.
It can be shown that there are no other paths with a higher safeness factor.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/07/02/example3.png" style="width: 362px; height: 242px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The path depicted in the picture above has a safeness factor of 2 since:
- The closest cell of the path to the thief at cell (0, 3) is cell (1, 2). The distance between them is | 0 - 1 | + | 3 - 2 | = 2.
- The closest cell of the path to the thief at cell (3, 0) is cell (3, 2). The distance between them is | 3 - 3 | + | 0 - 2 | = 2.
It can be shown that there are no other paths with a higher safeness factor.
</pre>

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

<ul>
	<li><code>1 &lt;= grid.length == n &lt;= 400</code></li>
	<li><code>grid[i].length == n</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
	<li>There is at least one thief in the <code>grid</code>.</li>
</ul>

class Solution {
public:
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        this->n = grid.size();
        vector<vector<int>> safenessGrid = getSafenessGrid(grid);
        return findSafestPath(safenessGrid);
    }

private:
    struct Position {
        int r,c;
        Position(int r, int c) : r(r), c(c) {}
        Position operator+(const pair<int,int>& other) const {
            return Position(r + other.first, c + other.second);
        }
    };

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

    bool isInBound(Position pos){
        return (pos.r >= 0) && (pos.c >= 0) && (pos.r < this->n) && (pos.c < this->n);
    }

    vector<vector<int>> getSafenessGrid(vector<vector<int>>& grid) {
        vector<vector<int>> safenessGrid(this->n, vector<int>(this->n, 0));
        queue<Position> q;

        // init safenessGrid
        for(int i=0; i<this->n; i++){
            for(int j=0; j<this->n; j++){
                if(grid[i][j]==1) {
                    q.push(Position(i,j));
                    safenessGrid[i][j] = 0;
                }
                else {
                    safenessGrid[i][j] = -1; //unvisited
                }
            }
        }

        //update safenessGrid
        while(!q.empty()) {
            Position pos = q.front();
            q.pop();

            for(const auto& direction : directions){
                Position nextPos = pos + direction;
                if(isInBound(nextPos) && safenessGrid[nextPos.r][nextPos.c] == -1) {
                    safenessGrid[nextPos.r][nextPos.c] = safenessGrid[pos.r][pos.c] + 1;
                    q.push(nextPos);
                }
            }
        }
        return safenessGrid;
    }

    int findSafestPath(vector<vector<int>>& safenessGrid) {
        auto cmp = [](const std::pair<int, Position>& a, const std::pair<int, Position>& b) {
            return a.first < b.first;
        };

        // Since we have a defined start and end point, we can use bidirectional BFS
        // instead of the standard BFS for greater efficiency.

        priority_queue<pair<int, Position>, vector<pair<int, Position>>, decltype(cmp)> pqStart(cmp);
        priority_queue<pair<int, Position>, vector<pair<int, Position>>, decltype(cmp)> pqEnd(cmp);

        vector<vector<bool>> visitedFromStart(n, vector<bool>(n, false));
        vector<vector<bool>> visitedFromEnd(n, vector<bool>(n, false));

        vector<vector<int>> safenessFromStart(n, vector<int>(n, INT_MIN));
        vector<vector<int>> safenessFromEnd(n, vector<int>(n, INT_MIN));

        pqStart.push({safenessGrid[0][0], Position(0, 0)});
        pqEnd.push({safenessGrid[n-1][n-1], Position(n-1, n-1)});
        safenessFromStart[0][0] = safenessGrid[0][0];
        safenessFromEnd[n-1][n-1] = safenessGrid[n-1][n-1];

        while (!pqStart.empty() && !pqEnd.empty()) {
            // Expand from the start side
            if (!pqStart.empty()) {
                auto [safeness, pos] = pqStart.top();
                pqStart.pop();
                visitedFromStart[pos.r][pos.c] = true;

                // Find a path!
                if (visitedFromEnd[pos.r][pos.c]) {
                    return min(safeness, safenessFromEnd[pos.r][pos.c]);
                }

                for (const auto& direction : directions) {
                    Position nextPos = pos + direction;
                    if (isInBound(nextPos) && !visitedFromStart[nextPos.r][nextPos.c]) {
                        int newSafeness = min(safeness, safenessGrid[nextPos.r][nextPos.c]);
                        if (newSafeness > safenessFromStart[nextPos.r][nextPos.c]) {
                            safenessFromStart[nextPos.r][nextPos.c] = newSafeness;
                            pqStart.push({newSafeness, nextPos});
                        }
                    }
                }
            }

            // Expand from the end side
            if (!pqEnd.empty()) {
                auto [safeness, pos] = pqEnd.top();
                pqEnd.pop();
                visitedFromEnd[pos.r][pos.c] = true;

                // Find a path!
                if (visitedFromStart[pos.r][pos.c]) {
                    return min(safeness, safenessFromStart[pos.r][pos.c]);
                }

                for (const auto& direction : directions) {
                    Position nextPos = pos + direction;
                    if (isInBound(nextPos) && !visitedFromEnd[nextPos.r][nextPos.c]) {
                        int newSafeness = min(safeness, safenessGrid[nextPos.r][nextPos.c]);
                        if (newSafeness > safenessFromEnd[nextPos.r][nextPos.c]) {
                            safenessFromEnd[nextPos.r][nextPos.c] = newSafeness;
                            pqEnd.push({newSafeness, nextPos});
                        }
                    }
                }
            }
        }
        return -1;
    }
};
161631