多源广度优先搜索

广度优先搜索

通过一道题目地图分析，来讲解和实践BFS。

原理

考虑最朴素的方法，即求出每一个海洋区域（grid[i][j] == 0 的区域）的「最近陆地区域」，然后记录下它们的距离，然后在这些距离里面取一个最大值。

对于一个给定的区域 (x, y)(x,y) ，求它的「最近陆地区域」，可以使用宽度优先搜索思想。我们把每个区域的坐标作以及这个区域与 (x, y)(x,y) 的曼哈顿距离为搜索状态，即 Coordinate 结构体的 x、y 和 step 属性。findNearestLand 方法实现了宽度优先搜索的过程，我们用一个 vis[u][v] 数组记录 (u, v)(u,v) 区域是否被访问过，在拓展新状态的时候按照如下四个方向：

(x - 1, y)(x−1,y)
(x, y + 1)(x,y+1)
(x + 1, y)(x+1,y)
(x, y - 1)(x,y−1)
在这里我们可以把四个方向定义为常量增量数组 dx 和 dy。

思考：我们需不需要搜索到队列为空才停止 BFS ？ 答案是不需要。当我们搜索到一个新入队的区域它的 grid 值为 1，即这个区域是陆地区域的时候我们就可以停止搜索，因为 BFS 能保证当前的这个区域是最近的陆地区域（BFS 的性质决定了这里求出来的一定是最短路）。

findNearestLand如果我们找不不到任何一个点是陆地区域则返回 -1。最终我们把 ans 的初始值置为 -1，然后与所有的 BFS 结果取最大。

实现

代码实现如下。

/**
 * @param {number[][]} grid
 * @return {number}
 */

const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
let n, m;

const findNearestLand = (x, y, grid) => {
    let vis = {};
    let q = [];
    q.push({x, y, step: 0});
    vis[`${x}${y}`] = 1;
    while(q.length > 0) {
        let f = q.shift();
        for (let i = 0; i < 4; i++) {
            const nx = f.x + dx[i], ny = f.y + dy[i];
            if (!(nx >= 0 && nx <= n -1 &&  ny >= 0 && ny <= m - 1)) {
                continue;
            }
            if (!vis[`${nx}${ny}`]) {
                if (grid[nx][ny]) {
                    return f.step + 1;
                }
                q.push({ x: nx, y: ny, step: f.step + 1 });
                vis[`${nx}${ny}`] = 1;
            }
        }
    }
    return -1;
};

var maxDistance = function(grid) {
    n = grid.length;
    m = grid[0].length;
    let ans = -1;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (!grid[i][j]) {
                ans = Math.max(ans, findNearestLand(i, j, grid));
            }
        }
    }
    return ans;
};

上述代码的核心就是遍历每一个海洋节点，计算离它最近的陆地节点的距离，这个计算过程使用的就是BFS，如果搜索完成还找不到就返回-1。

多源BFS

原理

所谓的多源bfs，其实就是在bfs的基础上创建一个虚拟的超级源点，这个源点连接向你想要作为多源源点的所有节点，这样一开始的时候按照单源思路，我们应该将超级源点加入队列，然后超级源点出队的时候，所有的实际源点进入队列，这个效果与一开始就将所有源点加入队列效果是相同的。

实现

题目：https://leetcode-cn.com/problems/01-matrix/

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var updateMatrix = function(matrix) {
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    const [m, n] = [matrix.length, matrix[0].length];
    let dist = [], seen = [];
    let q = [];

    for (let i = 0; i < m; i++) {
        dist[i] = [];
        seen[i] = [];
        for (let j = 0; j < n; j++) {
            dist[i][j] = seen[i][j] = 0;
            if (matrix[i][j] === 0) {
                q.push([i, j]);
                seen[i][j] = 1;
            }
        }
    }

    while(q.length > 0) {
        const [i, j] = q.shift();
        for (let k = 0; k < 4; k++) {
            const nx = i + dx[k], ny = j + dy[k];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !seen[nx][ny]) {
                dist[nx][ny] = dist[i][j] + 1;
                q.push([nx, ny]);
                seen[nx][ny] = 1;
            }
        }
    }
    return dist;
};