関小君刷题记

题目大意：

最短的桥

在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

返回必须翻转的 0 的最小数目。（可以保证答案至少是 1。）

示例 1：

输入：[[0,1],[1,0]]
输出：1

示例 2：

输入：[[0,1,0],[0,0,0],[0,0,1]]
输出：2

示例 3：

输入：[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1

提示：

1. 1 <= A.length = A[0].length <= 100
2. A[i][j] == 0 或 A[i][j] == 1

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=934

解题思路：

读完题目后第一反应就是dfs，bfs的解法，事实证明也是正确的。对于dfs，bfs的应用，之前的文章也有介绍过，这里再稍微啰嗦两句。这两种算法都是遍历网络中节点的方法，不同的是dfs被称为深度搜索，简单来说就是顺着一条路径一路走到黑，不撞南墙不回头，然后再返回当前的上一个节点继续。这是典型的递归逻辑。用本题来举例说明一下。比如，在一个2维数组中，对于任意一个点A[i][j]，它都可以向上下左右四个方向移动，移动之后的点同样存在4中可以移动的方向。我们用递归来实现深度搜索的方法大体如下：

private void dfs(int[][] A, int i, int j) {
        // 撞到墙了，一条递归路线结束
        if (i < 0 || i >= A.length || j < 0 || j >= A[0].length) {
            return;
        }
        dfs(A, i + 1, j); // 向右
        dfs(A, i - 1, j); // 向左
        dfs(A, i, j + 1); // 向下
        dfs(A, i, j - 1); // 向上
    }

再来说下bfs，相对于深度搜索，bfs属于广度搜索，还是用本题来举例子。比如我们已经找到了一条路径，然后以这条路径上的所有点作为起点，一圈一圈的向四周扩散，直到遍历完所有节点。

回到本题，大体思路应该为：

1. 先找到一个岛的起点，这个起点可以是这个岛任意的一个位置，也就是为1的位置。
2. 使用dfs遍历出该岛所有的节点，同时为了与另一个岛区分开，我们将该岛所有的值从1变为2。
3. 以第一个岛的所有点为起始位置，向每个点的四周扩散一步（即bfs），将新开拓到的节点（值为0的节点）数值变为2，再以这个新开拓出来的所有节点为起始，继续向四周扩散，直到发现数值为1的节点，说明找到了第二个岛屿的边缘，因为第二个岛屿的边缘不包含在桥的范围内，所以bfs使用的步数减一即为最短路径。

看下完整代码：

List<int[]> firstIsland = new ArrayList<>(); // 记录第一个岛屿的所有节点

public int shortestBridge(int[][] A) {
    // 先用dfs找到第一个岛屿的所有节点，记录到firstIsland中
    findFirstIsland(A);
    // 返回结果。
    int res = 0;
    // 开始bfs，一圈一圈的遍历，bfs的最长距离应该是2维数组的长加宽
    // 这一层循环直接使用white(true)也可以，
    // 因为肯定存在两个岛屿，当找到第二个岛时会结束循环，所以不会出现死循环
    for (int count = 0; count < (A.length + A[0].length); count++) {
        // 用于记录新开拓出来的与第一个岛屿相连的区域
        List<int[]> bridge = new ArrayList<>();
        // 循环遍历第一个岛所有节点
        for (int[] point : firstIsland) {
            int i = point[0]; // 节点的i坐标（横坐标） 
            int j = point[1]; // 节点的j坐标（纵坐标）
            // 当前节点横坐标加一，如果不越界，则：
            if (i + 1 < A.length) {
                // 下个节点是1，说明找到了第二个岛，返回res。
                if (A[i + 1][j] == 1) {
                    return res;
                } 
                // 下个节点是0，说明还未找到第二个岛。
                else if (A[i + 1][j] == 0) {
                    // 将下个节点设置为2
                    A[i + 1][j] = 2;
                    // 同时将下个节点保存至bridge中，用于下一圈的遍历
                    bridge.add(new int[] { i + 1, j });
                }
            }
            // 当前节点横坐标减一，如果不越界，则：
            if (i - 1 >= 0) {
                if (A[i - 1][j] == 1) {
                    return res;
                } else if (A[i - 1][j] == 0) {
                    A[i - 1][j] = 2;
                    bridge.add(new int[] { i - 1, j });
                }
            }
            // 当前节点纵坐标加一，如果不越界，则：
            if (j + 1 < A.length) {
                if (A[i][j + 1] == 1) {
                    return res;
                } else if (A[i][j + 1] == 0) {
                    A[i][j + 1] = 2;
                    bridge.add(new int[] { i, j + 1 });
                }
            }
            // 当前节点纵坐标减一，如果不越界，则：
            if (j - 1 >= 0) {
                if (A[i][j - 1] == 1) {
                    return res;
                } else if (A[i][j - 1] == 0) {
                    A[i][j - 1] = 2;
                    bridge.add(new int[] { i, j - 1 });
                }
            }
        }
        // 重置数据，进行下一圈bfs
        firstIsland.clear();
        firstIsland.addAll(bridge);
        bridge.clear();
        // 步数加一
        res++;
    }
    return res;
}

private void findFirstIsland(int[][] A) {
    // 顺序循环2维数组A，直到找到第一个为1的节点
    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < A[i].length; j++) {
            if (A[i][j] == 1) {
                firstIsland.add(new int[] { i, j });
                // 从当前节点开始dfs，找到第一个岛屿所有节点
                dfs(A, i, j);
                return;
            }
        }
    }
}

private void dfs(int[][] A, int i, int j) {
    // 越界判断
    if (i < 0 || i >= A.length || j < 0 || j >= A[0].length) {
        return;
    }
    // 如果当前节点为1，继续dfs
    if (A[i][j] == 1) {
        // 为了与第二个岛屿进行区分，将当前岛屿的值从1变为2
        A[i][j] = 2;
        // 将当前节点保存至firstIsland
        firstIsland.add(new int[] { i, j });
        dfs(A, i + 1, j); // 从当前节点向右dfs
        dfs(A, i - 1, j); // 从当前节点向左dfs
        dfs(A, i, j + 1); // 从当前节点向下dfs
        dfs(A, i, j - 1); // 从当前节点向上dfs
    }
}

本题解法用时11ms

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-934-shortest-bridge解题思路分析/