<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:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        """
        Approach #1: calculate the minimum Manhattan distances
        to the nearest thief at each cell by going through each
        of the thieves and moving one cell away from it at a time
        and updating the distances as you go along.
        Then DFS from the start to the end, exploring branches
        that have equally distant nearest thieves and discarding
        branches that have closer nearest thieves.
        Time complexity: O(T * m * n + m * n) = O(T * m * n)

        Approach #2: find all the thieves and store in a set.
        BFS from each thief to find the minimum distance to a thief from each cell.
        DFS from start to finish and look for the path that maximizes
        the safeness score by looking up the Manhattan distances to the nearest thief.
        Discard branches that have maximum safeness distances less than the current maximum.
        Time complexity: O(T * m * n)
        Space complexity: O(T)

        Approach #3: apply A* with a cost function of the minimum Manhattan 
        distance to any of the thieves.
        Time complexity: O(4 ^ length of the final path)
        Space complexity: O(4 ^ length of the final path)

        Approach #4: BFS with binary search.
        - BFS from each thief to calculate the distance to the nearest thief at each cell.
        - Binary search based on the safeness factor `v` in the range (0,2n). For each v:
            - DFS from (0,0) to (n-1,n-1) and check if there is a path that does not contain and cells
            for which the nearest thief is closer than v.
            - If there is a path, update the maximum safeness factor found so far.
        - Return the maximum v.
        """

        n = len(grid)
        safeness_grid = [[float('inf') for _ in range(n)] for _ in range(n)]

        q = deque()
        for i in range(n):
            for j in range(n):
                if grid[i][j]:
                    safeness_grid[i][j] = 0
                    q.append(((i,j),0))

        max_safeness = 0
        while q:
            (tr, tc), safeness = q.popleft()
            for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                r = tr + dr
                c = tc + dc
                if (
                    0 <= r < n 
                    and 0 <= c < n 
                    and safeness + 1 < safeness_grid[r][c]
                ):
                    safeness_grid[r][c] = safeness + 1
                    max_safeness = max(max_safeness, safeness + 1)
                    q.append([(r,c), safeness + 1])

        def has_path_with_safeness(v):
            if safeness_grid[0][0] < v or safeness_grid[n-1][n-1] < v:
                return False
            stack = [(0,0)]
            visited = set()
            while stack:
                r,c = stack.pop()
                visited.add((r,c))
                if r == c == n-1:
                    return True
                for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                    nr = r + dr
                    nc = c + dc
                    if (
                        0 <= nr < n
                        and 0 <= nc < n 
                        and (nr,nc) not in visited
                        and safeness_grid[nr][nc] >= v
                    ):
                        stack.append((nr,nc))
            return False

        safest_path = 0
        left, right = 0, max_safeness
        while left <= right:
            mid = (left + right) // 2
            if has_path_with_safeness(mid):
                safest_path = mid
                left = mid + 1
            else:
                right = mid - 1
        return safest_path

4791