1162. 地图分析

[zpc7]

1162. 地图分析
参考题解: https://leetcode.cn/problems/as-far-from-land-as-possible/solution/jian-dan-java-miao-dong-tu-de-bfs-by-sweetiee/

/**
 * @param {number[][]} grid
 * @return {number}
 */
const maxDistance = grid => {
    // 存储四个方向的横纵坐标向量, eg:(0, 1)代表向上, 以此类推
    const dx = [0, 0, 1, -1]
    const dy = [1, -1, 0, 0]

    // 模拟一个队列
    const queue = [];
    // 单元格行数和列数
    const row = grid.length;
    const col = grid[0].length;

    // 初始化队列
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            // 将所有的陆地(1)入列
            if (grid[i][j] === 1) {
                queue.push([i, j]);
            }
        }
    }

    // 从各个陆地开始，一圈一圈的遍历海洋，最后遍历到的海洋就是离陆地最远的海洋
    // 是否有海洋(0)
    let hasOcean = false;
    // 当前队列中处理的陆地元素
    let point = [];
    while (!!queue.length) {
        point = queue.shift(); // 队列头部的元素出列
        let [x, y] = point;
        // 取出队列的元素，将其四周的海洋入队(for中的4 代表4个方向)
        for (let i = 0; i < 4; i++) {
            let newX = x + dx[i];
            let newY = y + dy[i];
            // 坐标越界或不是海洋, 就跳出循环
            if (newX < 0 || newX >= row || newY < 0 || newY >= col || grid[newX][newY] !== 0) {
                continue;
            }
            // 否则就将这个区域扩展层数+1
            // 这里我直接修改了原数组，因此就不需要额外的数组来标志是否访问
            grid[newX][newY] = grid[x][y] + 1;
            hasOcean = true;
            // 将新的区域放入队列(BFS的思路)
            queue.push([newX, newY]);
        }
    }

    // 没有陆地或者没有海洋，返回-1
    if (point.length == 0 || !hasOcean) {
        return -1;
    }

    // 返回最后一次遍历到的海洋的距离
    return grid[point[0]][point[1]] - 1;

}