题目大意：
最短的桥
在给定的二维二进制数组 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 <= A.length = A[0].length <= 100A[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的位置。
- 使用dfs遍历出该岛所有的节点，同时为了与另一个岛区分开，我们将该岛所有的值从1变为2。
- 以第一个岛的所有点为起始位置，向每个点的四周扩散一步（即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解题思路分析/