About

当有人告诉我说刷题只是为了面试其实我是不赞同的，我认为刷题一方面提升了自己数据结构与算法的知识储备，另一方面也是最重要的一点是提高了我们的建模能力，也就是说我们如何把一个需求或者一个问题转化为一个数学模型，然后通过算法去解决这个问题。
我认为，当我们处在编程初级阶段时候，我们最缺乏的，最应该学的不是各种写业务代码的技能，而是培养自己用编程解决问题的能力，就好比大多数人认为学习数学没什么用，因为你去买菜的时候是不会用积分来帮你省钱的，但我认为这样的想法是错误的，不是数学没用，而是因为你没有针对实际问题建立数学模型的能力，你都没有把一个实际问题转化成一个数学模型，你又怎么用数学去解决这个问题呢？

1. 题目

你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。

我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。

如果我们的地图上只有陆地或者海洋，请返回 -1。

示例 1：

输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。
示例 2：

输入：[[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释：
海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/as-far-from-land-as-possible

2. 解题思路

当拿到这道题的时候其实我是懵逼的，可能是我比较笨，我没有想到怎么样去找这个符合要求的点，看过官方题解后才有了一定的思路。。。然后，我认为解题的关键是，我们要把这道题翻译一下，这道题的目的是让我们找出离陆地最远的海洋，那么就是说让我们找到一片海域，这片海域到陆地的最短距离是所有海域到陆地最短距离中最长的！是不是有点绕，哈哈。所以，解决这道题的关键就在于，我们要从所有的陆地节点同时出发，然后去访问未访问过的海域，当最后一片海域被访问到的时候，就说明这块海域是离所有陆地节点最远的那片海域。
这道题用到了图的多源广度优先搜索，图的BFS和树的BFS不同的地方在于我们开始搜索时源节点的数量，树的源节点就是根节点，只有1个，而图就不一样了，我们可以从任意多个点开始展开搜索~
思路是这样的：首先遍历这个地图，然后把陆地，也就是grid[i][j] == 1的坐标push到一个队列中，然后以该队列里的源节点展开搜索，我这里用了一个技巧，就是我没有把所有的节点都放在一个队列中，而是把同一层的节点放在一个队列中，这样的话我们就可以知道搜索了多少轮，然后因为每搜索一轮就是向前走了一步，所以可以直接记录为曼哈顿距离的增长，最后当队列为空的时候返回搜索的轮数就是我们要的离所有陆地节点最远的距离了。另外需要注意的地方就是，访问过的节点需要记录，否则会重复访问。

2.1 代码

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
    let res = -1
    for (let x = 0; x < grid.length; x++) {
        for (let y = 0; y < grid[0].length; y++) {
            res = Math.max(res, bfs(grid, x, y))
        }
    }
    return res ? res : -1
};

function bfs (map, x, y) {
    const queue = [[x, y]]
    const _map = JSON.parse(JSON.stringify(map))
    while (queue.length) {
        const [i, j] = queue.shift()
        if (i-1 > -1) {
            if (_map[i-1][j] == 0) {
                _map[i-1][j] = 2
                queue.push([i-1, j])
            } else if (_map[i-1][j] == 1) return Math.abs(x - i + 1) + Math.abs(y - j)
        }
        if (i+1 < _map.length) {
            if ( _map[i+1][j] == 0) {
                _map[i+1][j] = 2
                queue.push([i+1, j])
            } else if (_map[i+1][j] == 1) return Math.abs(x - i -1) + Math.abs(y - j)
        }
        if (j-1 > -1) {
            if ( _map[i][j-1] == 0) {
                _map[i][j-1] = 2
                queue.push([i, j-1])
            } else if (_map[i][j-1] == 1) return Math.abs(x - i) + Math.abs(y - j + 1) 
            
        }
        if (j+1 > _map[0].length) {
            if ( _map[i][j+1] == 0) {
                _map[i][j+1] = 2
                queue.push([i, j+1])
            } else if ( _map[i][j+1] == 1) return Math.abs(x - i) + Math.abs(y - j - 1) 
            
        }
    }
    return 0
}

2.2 性能

0SFXQ9GK)$X{FJ8SCO)5DZL.png