1765. 地图中的最高点 : 多源 BFS 运用题

输入：isWater = [[0,1],[0,0]]
输出：[[1,0],[2,1]]
解释：上图展示了给各个格子安排的高度。
蓝色格子是水域格，绿色格子是陆地格。
复制代码

输入：isWater = [[0,0,1],[1,0,0],[0,0,0]]
输出：[[1,1,0],[0,1,1],[1,2,2]]
解释：所有安排方案中，最高可行高度为 2 。
任意安排方案中，只要最高高度为 2 且符合上述规则的，都为可行方案。
复制代码

class Solution {
    public int[][] highestPeak(int[][] g) {
        int m = g.length, n = g[0].length;
        int[][] ans = new int[m][n];
        Deque<int[]> d = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1) d.addLast(new int[]{i, j});
                ans[i][j] = g[i][j] == 1 ? 0 : -1;
            }
        }
        int[][] dirs = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}};
        int h = 1;
        while (!d.isEmpty()) {
            int size = d.size();
            while (size-- > 0) {
                int[] info = d.pollFirst();
                int x = info[0], y = info[1];
                for (int[] di : dirs) {
                    int nx = x + di[0], ny = y + di[1];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    if (ans[nx][ny] != -1) continue;
                    ans[nx][ny] = h;
                    d.addLast(new int[]{nx, ny});
                }
            }
            h++;
        }
        return ans;
    }
}
复制代码

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        m, n = len(isWater), len(isWater[0])
        ans = [[0] * n for _ in range(m)]
        d = deque()
        for i in range(m):
            for j in range(n):
                if isWater[i][j]:
                    d.append((i, j))
                ans[i][j] = 0 if isWater[i][j] else -1
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        h = 1
        while d:
            size = len(d)
            for _ in range(size):
                x, y = d.popleft()
                for di in dirs:
                    nx, ny = x + di[0], y + di[1]
                    if 0 <= nx < m and 0 <= ny < n and ans[nx][ny] == -1:
                        ans[nx][ny] = h
                        d.append((nx, ny))
            h += 1
        return ans
复制代码

func highestPeak(isWater [][]int) [][]int {
    m, n := len(isWater), len(isWater[0])
    ans, d := make([][]int, m), [][]int{}
    for i := 0; i < m; i++ {
        ans[i] = make([]int, n)
        for j := 0; j < n; j++ {
            if isWater[i][j] == 1 {
                d = append(d, []int{i, j})
                ans[i][j] = 0
            } else {
                ans[i][j] = -1
            }
        }
    }
    dirs := [][]int{{1,0}, {-1,0}, {0,1}, {0,-1}}
    for h := 1; len(d) > 0; h++ {
        for size := len(d); size > 0; size--{
            info := d[0]
            d = d[1:]
            x, y := info[0], info[1]
            for _, di := range dirs {
                nx, ny := x + di[0], y + di[1]
                if nx >= 0 && nx < m && ny >= 0 && ny < n && ans[nx][ny] == -1 {
                    ans[nx][ny] = h
                    d = append(d, []int{nx, ny})
                }
            }
        }
    }
    return ans
}
复制代码

const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& g) {
        int n = g.size(), m = g[0].size();
        queue<pair<int, int>> q;
        vector<vector<int>> ans(n, vector<int>(m, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (g[i][j] == 1) {
                    q.emplace(i, j);
                } else {
                    ans[i][j] = -1;
                }
            }
        }
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int a = x + dx[i], b = y + dy[i];
                if (a < 0 || a == n || b < 0 || b == m) continue;
                if (ans[a][b] >= 0) continue;
                ans[a][b] = ans[x][y] + 1;
                q.emplace(a, b);
            }
        }
        return ans;
    }
};
复制代码