2812. Find the Safest Path in a Grid Medium

1/**
2 * [2812] Find the Safest Path in a Grid
3 *
4 * You are given a 0-indexed 2D matrix grid of size n x n, where (r, c) represents:
5 * 
6 * 	A cell containing a thief if grid[r][c] = 1
7 * 	An empty cell if grid[r][c] = 0
8 * 
9 * You are initially positioned at cell (0, 0). In one move, you can move to any adjacent cell in the grid, including cells containing thieves.
10 * The safeness factor of a path on the grid is defined as the minimum manhattan distance from any cell in the path to any thief in the grid.
11 * Return the maximum safeness factor of all paths leading to cell (n - 1, n - 1).
12 * An adjacent cell of cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) and (r - 1, c) if it exists.
13 * The Manhattan distance between two cells (a, b) and (x, y) is equal to |a - x| + |b - y|, where |val| denotes the absolute value of val.
14 *  
15 * <strong class="example">Example 1:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2023/07/02/example1.png" style="width: 362px; height: 242px;" />
17 * Input: grid = [[1,0,0],[0,0,0],[0,0,1]]
18 * Output: 0
19 * Explanation: All paths from (0, 0) to (n - 1, n - 1) go through the thieves in cells (0, 0) and (n - 1, n - 1).
20 * 
21 * <strong class="example">Example 2:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2023/07/02/example2.png" style="width: 362px; height: 242px;" />
23 * Input: grid = [[0,0,1],[0,0,0],[0,0,0]]
24 * Output: 2
25 * Explanation: The path depicted in the picture above has a safeness factor of 2 since:
26 * - 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.
27 * It can be shown that there are no other paths with a higher safeness factor.
28 * 
29 * <strong class="example">Example 3:
30 * <img alt="" src="https://assets.leetcode.com/uploads/2023/07/02/example3.png" style="width: 362px; height: 242px;" />
31 * Input: grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
32 * Output: 2
33 * Explanation: The path depicted in the picture above has a safeness factor of 2 since:
34 * - 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.
35 * - 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.
36 * It can be shown that there are no other paths with a higher safeness factor.
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	1 <= grid.length == n <= 400
42 * 	grid[i].length == n
43 * 	grid[i][j] is either 0 or 1.
44 * 	There is at least one thief in the grid.
45 * 
46 */
47pub struct Solution {}
48
49// problem: https://leetcode.com/problems/find-the-safest-path-in-a-grid/
50// discuss: https://leetcode.com/problems/find-the-safest-path-in-a-grid/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54impl Solution {
55    pub fn maximum_safeness_factor(grid: Vec<Vec<i32>>) -> i32 {
56        0
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_2812() {
68    }
69}
70