给定一个二维 0-1 矩阵，其中 1 表示陆地，0 表示海洋，每个位置与上下左右相连。已知矩阵中有且只有两个岛屿，求最少要填海造陆多少个位置才可以将两个岛屿相连。_输入一个01矩阵,1代表是草地,0代表普通地面, 如果两个1相邻,那么这两个1属于同一

给定一个二维 0-1 矩阵，其中 1 表示陆地，0 表示海洋，每个位置与上下左右相连。已知矩阵中有且只有两个岛屿，求最少要填海造陆多少个位置才可以将两个岛屿相连。
输入是一个二维整数数组，输出是一个非负整数，表示需要填海造陆的位置数。

function func(arr) {
    // n * n 的地图
    const n = arr.length;
    const nums = [-1, 0, 1, 0, -1];
    const visited = [];
    for (let i = 0; i < n; ++i) {
        visited[i] = new Array(n).fill(false);
    }

    // 获取岛屿的范围
    const _getLandArea = (i, j, land) => {
        // 数组越界或非陆地或已经计算过，退出
        if (i < 0 || i >= n 
            || j < 0 || j >= n 
            || arr[i][j] != 1 
            || visited[i][j]) {
            return;
        }

        // 标记当前位置为已计算
        visited[i][j] = true;
        land.push({ x: i, y: j });

        // 当前坐标尝试向四个方位拓展
        for (let k = 0; k < 4; ++k) {
            _getLandArea(i + nums[k], j + nums[k + 1], land);
        }
    };

    // 寻找岛屿
    const _getLand = () => {
        const land = [];
        // 标识此次是否已寻找到岛屿
        let findLand = false;
        // 尝试获取岛屿
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < n; ++j) {
                // 如果是岛屿且未计算过
                if (arr[i][j] == 1 && !visited[i][j]) {
                    // 获取该岛屿的范围
                    _getLandArea(i, j, land);
                    findLand = true;
                    break;
                }
            }

            // 此次已寻找到岛屿，退出
            if (findLand) {
                break;
            }
        }

        return land;
    };

    // 岛屿A
    const landA = _getLand();
    // 岛屿B
    const landB = _getLand();

    /**
     * 计算两个岛屿之间的最短路径，即判断其中两个点 a (x1, y1)和 b (x2, y2) 的最短距离
     * 因为不能斜着走，所以应该是计算边长
     * 即 step = 长 + 宽 = Math.abs(x1 - x2) + Math.abs(y1 - y2) - 1
     */
    let minStep = Infinity;
    for (let i = 0; i < landA.length; ++i) {
        for (let j = 0; j < landB.length; ++j) {
            const step = Math.abs(landA[i].x - landB[j].x) + Math.abs(landA[i].y - landB[j].y) - 1;
            minStep = Math.min(minStep, step);
        }
    }

    return { landA, landB, step: minStep };
}

const arr = [
    [ 1, 0, 0, 0, 0 ],
    [ 0, 0, 0, 1, 0 ],
    [ 0, 0, 1, 1, 0 ],
    [ 0, 0, 1, 1, 0 ],
    [ 0, 0, 0, 0, 0 ],
];
const result = func(arr);

console.log(result);
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86