2022.01.29 - 223.地图中的最高点

2022.01.29 - 223.地图中的最高点

文章目录

1. 题目2. 思路

(1) 多源BFS 3. 代码

1. 题目

2. 思路 (1) 多源BFS

将所有水域先加入队列中，即可对所有水域同时向外计算陆地高度。 3. 代码

import java.util.linkedList;
import java.util.Queue;

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length;
        int n = isWater[0].length;
        int[][] height = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 0) {
                    height[i][j] = -1;
                }
            }
        }
        Queue queue = new linkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] ints = queue.poll();
            int i = ints[0];
            int j = ints[1];
            if (i > 0 && height[i - 1][j] == -1) {
                height[i - 1][j] = height[i][j] + 1;
                queue.offer(new int[]{i - 1, j});
            }
            if (i < m - 1 && height[i + 1][j] == -1) {
                height[i + 1][j] = height[i][j] + 1;
                queue.offer(new int[]{i + 1, j});
            }
            if (j > 0 && height[i][j - 1] == -1) {
                height[i][j - 1] = height[i][j] + 1;
                queue.offer(new int[]{i, j - 1});
            }
            if (j < n - 1 && height[i][j + 1] == -1) {
                height[i][j + 1] = height[i][j] + 1;
                queue.offer(new int[]{i, j + 1});
            }
        }
        return height;
    }
}