LeetCode - 1162 地图分析

题目来源

1162. 地图分析 - 力扣（LeetCode）

题目描述

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

示例

 

提示

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] 不是 0 就是 1

题目解析

这题的意思是，找到一个海域，保证该海域离所有的陆地最远。

如果我们假设陆地到本身的距离为0，而与陆地相邻的区域距离为1，依次递进，可以得到如下图所示

如果我们将陆地看成一个污水源，那么本题找距离陆地最远的海域问题，其实就是污水源的扩散问题，即合适可以将所有还需污染完。

从上面图示，可以看出：海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。

本题可以使用图的多源BFS来求解。

关于图的多源BFS可以参考华为机试 - 计算疫情扩散时间_伏城之外的博客-CSDN博客

算法源码

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
    // 将本题的陆地看成污水源，将海洋看成干净水域
    // queue用于保存将要扩散的污水源位置
    const queue = []
 
    // 遍历grid，找出第一批污水源位置
    const n = grid.length
    for(let i=0; i
        for(let j=0; j
            if(grid[i][j] === 1) {
                queue.push([i,j])
            }
        }
    }
 
    // seaCount用于保存初始时干净水域的个数
    let seaCount = n * n - queue.length
 
    // 如果初始时全部是污水源，或者全部是干净水域，则返回-1
    if(queue.length === 0 || seaCount === 0) {
        return -1
    }
 
    // 上下左右偏移量
    const offset = [[-1,0], [1,0], [0,-1], [0,1]]
 
    // dist用于保存最远距离，我这里还使用dist标记污水源，因此dist需要从2开始标记，因为1已经被题目来标记了，因此最终最远距离需要减去1
    let dist;
    // 当干净水域个数为0时，循环结束
    while(seaCount) {
        // 取出队头污水源位置
        const [x, y] = queue.shift()
        dist = grid[x][y] + 1
 
        // 遍历污水源位置的上下左右四个位置，若是干净水域，则将其污染
        for(let i=0; i<4; i++) {
            const [offsetX, offsetY] = offset[i]
            const newX = x + offsetX
            const newY = y + offsetY
            if(newX < 0 || newX >= n || newY < 0 || newY >= n) continue
            if(grid[newX][newY] === 0) {
                seaCount--
                grid[newX][newY] = dist
                // 新增的污染水域，将成为新的污染源
                queue.push([newX, newY])
            }
        }
    }
 
    return dist - 1
};