<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:
        # do a bfs from each thief and number places by the closest theif, choose place by minthievery at each spot once starting at every place
        n = len(grid)

        safety_level = [[0 for _ in range(n)] for _ in range(n)]

        # do an all bfs, safery level is whatever the first theif labels it as

        frontier = deque()
        seen = set()
        for r_i in range(n):
            for c_i in range(n):
                if grid[r_i][c_i] == 1:
                    frontier.append((r_i, c_i, 0))  # safety level
                    seen.add((r_i, c_i))

        # theif locations will now start as the frontier

        def get_valid_neighbors(r, c):
            # use seen from outer scope, and n. only do adj (no diag)
            neighs = []

            for r_change, c_change in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                new_r = r + r_change
                new_c = c + c_change
                if (new_r, new_c) not in seen and new_r >= 0 and new_r < n and new_c >= 0 and new_c < n:
                    neighs.append((new_r, new_c))
            return neighs

        while frontier:
            r, c, sl = frontier.popleft()
            safety_level[r][c] = sl
            for nr, nc in get_valid_neighbors(r, c):
                frontier.append((nr, nc, sl + 1))
                seen.add((nr, nc))


        # then do a DFS and backtrack whenever the number increases, once you backtrack to the source, decrease the acceptable safety that you will do through. Start the number at the minium theivery of the start and end

        min_safety_level = min(safety_level[0][0], safety_level[n-1][n-1])
        if min_safety_level == 0:
            return 0

        def get_valid_dfs_neighbors(r, c, acceptable_level, seen):
            # use seen from outer scope, and n. only do adj (no diag)
                neighs = []

                for r_change, c_change in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                    new_r = r + r_change
                    new_c = c + c_change
                    if (new_r, new_c) not in seen and new_r >= 0 and new_r < n and new_c >= 0 and new_c < n and safety_level[new_r][new_c] >= acceptable_level:
                        neighs.append((new_r, new_c))
                return neighs

        while min_safety_level > 0:
            dfs_queue = [(0, 0)]
            visited = set((r, c))

            while dfs_queue:
                r, c = dfs_queue.pop()
                new = get_valid_dfs_neighbors(r, c, min_safety_level, visited)
                for new_neigh in new:

                    visited.add((new_neigh[0], new_neigh[1]))
                    if new_neigh == (n-1, n-1):
                        return min_safety_level
                    else:
                        dfs_queue.append(new_neigh)
            
            # if we can't get to end with cur safety level
            min_safety_level -= 1


        return 0




4259