LeetCode - 1162 地图分析

r囧r小猫 2023-09-23 15:13 69阅读 0赞

#### 题目来源 ####

[1162. 地图分析 - 力扣（LeetCode）][1162. _ - _LeetCode]

#### 题目描述 ####

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

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

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

#### 示例 ####

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:59px;">输入</td> 
   <td style="width:439px;">grid = [[1,0,1],[0,0,0],[1,0,1]]</td> 
  </tr> 
  <tr> 
   <td style="width:59px;">输出</td> 
   <td style="width:439px;">2</td> 
  </tr> 
  <tr> 
   <td style="width:59px;">说明</td> 
   <td style="width:439px;"> <p>海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。</p> <p style="text-align:center;"><img alt="" src="https://img-blog.csdnimg.cn/img_convert/fd4c15abc33867ea9373b67ab44b5e15.jpeg">&nbsp;</p> </td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:59px;">输入</td> 
   <td style="width:439px;">grid = [[1,0,0],[0,0,0],[0,0,0]]</td> 
  </tr> 
  <tr> 
   <td style="width:59px;">输出</td> 
   <td style="width:439px;">4</td> 
  </tr> 
  <tr> 
   <td style="width:59px;">说明</td> 
   <td style="width:439px;"> <p>海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。</p> <p style="text-align:center;"><img alt="" src="https://img-blog.csdnimg.cn/img_convert/6eab07c76c74d6e39d51b94042eec26f.jpeg">&nbsp;</p> </td> 
  </tr> 
 </tbody> 
</table>

#### 提示 ####

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

#### 题目解析 ####

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

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

![f3f5e008644145cb8a3c23c1e0f418ca.png][]

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

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

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

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

#### 算法源码 ####

/**
     * @param {number[][]} grid
     * @return {number}
     */
    var maxDistance = function(grid) {
        // 将本题的陆地看成污水源，将海洋看成干净水域
        // queue用于保存将要扩散的污水源位置
        const queue = []
    
        // 遍历grid，找出第一批污水源位置
        const n = grid.length
        for(let i=0; i<n; i++) {
            for(let j=0; j<n; 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
    };

![215576c419094cb8af1ba6e8066a385f.png][]

[1162. _ - _LeetCode]: https://leetcode.cn/problems/as-far-from-land-as-possible/
[f3f5e008644145cb8a3c23c1e0f418ca.png]: https://img-blog.csdnimg.cn/f3f5e008644145cb8a3c23c1e0f418ca.png
[- _-CSDN]: https://blog.csdn.net/qfc_128220/article/details/127711317?spm=1001.2014.3001.5501
[215576c419094cb8af1ba6e8066a385f.png]: https://img-blog.csdnimg.cn/215576c419094cb8af1ba6e8066a385f.png