Multi-source Breadth First Search

Posted on Edited on In Waline:

Through a topic地图分析, to explain and practice BFS.

Principle

Consider the simplest method, which is to find each ocean area (grid [i] [j] 0 的区域）的「最近陆地区域」，然后记录下它们的距离，然后在这些距离里面取一个最大值。

For a given area (x, y) (x, y), we can use the Breadth First Search idea to find its “nearest land area”. We take the coordinates of each area and the Manhattan distance from this area to (x, y) (x, y) as the search state, that is, the x, y and step properties of the Coordinate structure. The findNearestLand method implements the process of Breadth First Search. We use a vis [u] [v] array to record whether the (u, v) (u, v) area has been visited. When expanding the new state, follow the following four directions:

(x - 1, y)(x−1,y)
(x, y + 1)(x,y+1)
(x + 1, y)(x+1,y)
(x, y - 1)(x,y−1)
Here we can define the four directions as constant delta arrays dx and dy.

Thinking: Do we need to search to find that the queue is empty to stop BFS? The answer is no. When we search for a newly joined area whose grid value is 1, that is, this area is a land area, we can stop the search, because BFS can guarantee that the current area is the nearest land area (the nature of BFS determines that what is found here must be the shortest path).

findNearestLand returns -1 if we can’t find any point that is a land area. Finally we set the initial value of ans to -1 and then take the maximum with all BFS results.

Achieve

The code implementation is as follows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * @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;
};

The core of the above code is to traverse each ocean node and calculate the distance to the nearest land node. This calculation process uses BFS. If the search is completed and cannot be found, it will return -1.

Multi-source BFS

Principle

The so-called multi-source bfs is actually to create a virtual super source point on the basis of bfs. This source point is connected to all nodes that you want to use as multi-source points. At the beginning, according to the single-source idea, we should The super source point is added to the queue, and then when the super source point is queued, all the actual source points enter the queue. This effect is the same as adding all source points to the queue at the beginning.

Achieve

title: https://leetcode-cn.com/problems/01-matrix/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * @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;
};