LeetCode每日一题(1162. As Far from Land as Possible)

Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

Example 1:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2

Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: grid = [[1,0,0],[0,0,0],[0,0,0]]
Output: 4

Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] is 0 or 1

---

impl Solution {
    pub fn max_distance(mut grid: Vec<Vec<i32>>) -> i32 {
        for i in 0..grid.len() {
            for j in 0..grid[0].len() {
                if grid[i][j] == 0 {
                    grid[i][j] = i32::MAX;
                    continue;
                }
                grid[i][j] = 0;
            }
        }
        loop {
            let mut modified = false;
            for i in 0..grid.len() {
                for j in 0..grid[0].len() {
                    let top = if i > 0 { grid[i - 1][j] } else { i32::MAX };
                    let bottom = if i < grid.len() - 1 {
                        grid[i + 1][j]
                    } else {
                        i32::MAX
                    };
                    let left = if j > 0 { grid[i][j - 1] } else { i32::MAX };
                    let right = if j < grid[0].len() - 1 {
                        grid[i][j + 1]
                    } else {
                        i32::MAX
                    };
                    let base = top.min(bottom).min(left).min(right);
                    if base == i32::MAX {
                        continue;
                    }
                    if grid[i][j] > base + 1 {
                        grid[i][j] = base + 1;
                        modified = true;
                    }
                }
            }
            if !modified {
                break;
            }
        }
        let ans = grid
            .into_iter()
            .map(|row| row.into_iter().max().unwrap())
            .max()
            .unwrap();
        if ans == 0 || ans == i32::MAX {
            return -1;
        }
        ans
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52