我们分别讲过了 DFS 和 BFS，现在来看一道综合例题。
接下来我们再看一道综合上节 DFS 和 BFS 的题
LeetCode 934
连接岛屿最短的桥
题目：给定一个二维 0-1 矩阵，其中 1 表示陆地，0 表示海洋，每个位置与上下左右相连。已知矩阵中有且只有两个岛屿，现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。（填海造陆）
求最少要填海造陆多少个位置才可以将两个岛屿相连。
示例 1：
输入：[[0,1],
[1,0]]
输出：1
解释：这个矩阵里的两座岛分别为右上（1）和左下（1）
现只需将左上（0）或右下（0）变为 1 （填海造陆），即可连接两块岛屿，所以返回为 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
思路
已知矩阵中有且只有两个岛屿，那么我们如何得到某块岛屿距离另一块岛屿的距离呢？
- 首先，我们应该先找到其中某一块岛屿
- 然后从这个岛屿出发，用 BFS 向外扩展找到另外一个岛屿
这里可能有小伙伴会有疑问：为什么用 BFS 向外扩，就能找到距离另外一个岛屿的最短路径呢？
因为如果我们已经知道了第一个岛屿的所有位置（所有的 1 ），那么 BFS 就会沿着已知的 1 ，一层一层的往外扩，一旦找到一个 1，那么往外扩的次数就是最短的了
那么我们如何先找到其中的某一块岛屿呢？
我们知道：矩阵中上下左右相连的 1 （陆地），组成一块岛屿
那么我们可以找到一块相连的 1 ，即可找到其中某一块岛屿
我们可以根据上一节的 DFS，从矩阵某一元素开始遍历：
- 是 0 我们就跳过
- 是 1 我们就递归的遍历它的上下左右以此找到和它相邻的陆地，进而找出整块岛屿
还记得我们上一节的 DFS 找岛屿最大面积怎么写的吗？
intdfs(int[][] grid, inti, intj){
if (i<0||j<0||i==grid.length||j==grid[i].length||grid[i][j] ==0)
return0;
grid[i][j] =0;
returndfs(grid, i-1, j) +dfs(grid, i+1, j) +dfs(grid, i, j-1) + dfs(grid, i, j+1) +1;
}
我们有三个参数
- grid数组
- 用来遍历二维数组的 i 和 j
今天这个题目，因为我们后续要用到 BFS ，并且需要记录当前陆地是否被访问过，所以这里的参数还需要增加：
- 队列 Queue （用于后续的 BFS）
- 布尔型二维数组 boolean [] [] visited（用于记录某块陆地是否被访问过）
我们可以改造一下上述的 dfs 递归函数：
voiddfs(int [][]A,inti,intj,Dequequeue,boolean[][]visited){
if(i<0||i>=A.length||j<0||j>=A[0].length||visited[i][j]
||A[i][j] !=1)
return;
visited[i][j] =true;
queue.add(newint[] {i,j});
dfs( A, i-1, j, queue, visited);
dfs( A, i+1, j, queue, visited);
dfs( A, i, j-1, queue, visited);
dfs( A, i, j+1, queue, visited);
}
上述代码的递归边界应该很好理解
visited[i][j] =true；
如果A[i] [j] == 1，那么会执行上一行代码，将此块陆地标记为已访问。
这里再说明下为什么我们的队列是Deque：
因为我们需要的队列里放的是某块陆地的坐标，即二维数组的某个位置
所以它里边放的实际上是一个数组（数组里只存有两个数 i 和 j ）
所以我们需要一个能存放数组的队列
这里选用 Deque（意思为双端队列，但双不双端跟我们这里没关系），是因为我们要的 ArrayDeque 实现了 Deque 接口，是其接口实现类
而 Deque 继承自 Queue
写出了 dfs递归函数，其它的也就好办了
我们回到主函数，主函数应该干什么呢？
publicintshortestBridge(int[][] A) {
?
}
回到之前思路提到的两步：
- 首先，我们应该先找到其中某一块岛屿（DFS）
- 然后从这个岛屿出发，用 BFS 向外扩展找到另外一个岛屿
我们从矩阵的第一个元素开始，用 DFS 来寻找到其中一个岛屿：
publicintshortestBridge(int[][] A){
Deque<int[]>queue=newArrayDeque<>();
intres=-1;
boolean[][] visited=newboolean[A.length][A[0].length];
booleanflag=true;
for(inti=0;i<A.length&&flag;i++){
for(intj=0;j<A[0].length;j++){
if(A[i][j] ==1){
dfs(A,i,j,queue,visited);
flag=false;
break;
}
}
}
}
按道理，我们只需要找到给定矩阵数组 A 里第一个出现的 1 即可，为什么呢？
- 因为给定矩阵里有且仅有两个岛屿，找到了一个 1 ，那么这个 1 （这块陆地）一定属于某块岛屿
- 所以只要找到第一个 1 ，我们把它交给 dfs 递归函数处理，dfs 就会用深度优先搜索递归遍历出所有与此 1 相邻的 1
- 这些 1 （陆地）存储在队列里的任务已经在 dfs里做了，所有直接将第一个 1 交由 dfs处理即可
仔细观察，为什么外层的 for循环 i 判断的那里还要加一个 flag 呢 ？
因为前文说了，这两层 for循环在这里的目的只是找到二维数组里出现的第一个 1 ， 我们不需要找到第二个（找到第二个及后续相连的 1 交由 dfs处理了），所以，在 dfs 递归函数的后面我们直接 break 掉了，但是 break 只能跳出当前循环，如何同时跳出外层循环呢？
- 对了，flag在这里正是这个意思，将 flag 赋为 false，下次外层判断时，就可以同时跳出外层循环了。
紧接着我们主函数里该怎么做呢？
我们用 dfs 递归函数找到了其中一块岛屿，并且将这块岛屿所有的陆地（给定二维数组里值为1）的坐标都放入了队列里
下一步我们开始出队这些陆地，并在每一块这些陆地基础上开始 bfs 广度搜索下一块岛屿
（跟我们上文基于队列的 bfs 代码非常相似了，只不过加了几句判断语句和赋值语句罢了）
while (!queue.isEmpty()){
intsize=queue.size();
res++;
for(inti=0;i<size;i++){
int[] item=queue.poll();
for(intj=0;j<4;j++){
intx=item[0] +direction[j]; //direction[]数组为上下左右四个方向（相连的陆地）
inty=item[1] +direction[j+1];
if(x<0||x>=A.length||y<0||y>=A[0].length
||visited[x][y]) continue;
if(A[x][y] ==1) returnres;
visited[x][y] =true;
queue.add(newint[] {x,y});
}
}
}
这里我们捎带提一下这个 direction[] 方向数组,其定义为：
int[] direction=newint[]{-1,0,1,0,-1};
“上下左右” 为四个方向为什么要定义五个数呢，而且为什么就是这几个数呢？
在这里我画个图大家就明白了
假设有一个int[] [] a = new int[3] [3]的二维数组，中间那个 0 的索引为a[1] [1]
那么它的上下左右位置的索引如下图所示：
所以下边两行代码也就很好理解了
intx=item[0] +direction[j];
inty=item[1] +direction[j+1]; //为什么要加1，因为保证二维坐标里一个变，一个不变
综上所述，我们在主函数里要干的事情也干完了
代码
下边给出完整代码，并附上注释
classSolution {
publicintshortestBridge(int[][] A) {
int[] direction=newint[]{-1,0,1,0,-1}; //定义上下左右四个方向
Deque<int[]>queue=newArrayDeque<>(); //定义装数组（二维数组坐标）的队列
intres=-1;
boolean[][] visited=newboolean[A.length][A[0].length]; //定义布尔型访问标记数组
booleanflag=true;
//从给定矩阵第一个元素开始遍历，寻找第一个1
for(inti=0;i<A.length&&flag;i++){
for(intj=0;j<A[0].length;j++){
if(A[i][j] ==1){
dfs(A,i,j,queue,visited); //找到第一个1，把它交由dfs递归函数处理，通过深度优先搜索遍历出临近的1（陆地）
flag=false; //标志置为false跳出外层循环
break; //跳出内层循环
}
}
}
//基于队列的bfs
while (!queue.isEmpty()){
intsize=queue.size();
res++;
for(inti=0;i<size;i++){
int[] item=queue.poll(); //检索并删除队列的头
for(intj=0;j<4;j++){
intx=item[0] +direction[j];//得到上下左右临近坐标
inty=item[1] +direction[j+1];//得到上下左右临近坐标
if(x<0||x>=A.length||y<0||y>=A[0].length
||visited[x][y]) continue;
if(A[x][y] ==1) returnres; //bfs找到第一个1即返回（最短路径）
visited[x][y] =true; //将访问过的进行标记
queue.add(newint[] {x,y});
}
}
}
returnres;
}
privatevoiddfs(int [][]A,inti,intj,Dequequeue,boolean[][]visited){
if(i<0||i>=A.length||j<0||j>=A[0].length||visited[i][j]
||A[i][j] !=1) // i,j不要越界，A[i][j]已经访问了或者A[i][j]等于0（非陆地）
return; //则返回空
visited[i][j] =true; //如果此块是陆地（为1），则标记为已访问过
queue.add(newint[] {i,j}); //并将其坐标加入到队列当中，以供后续进行bfs
//上下左右四个方向上分别进行深度优先搜索
dfs( A, i-1, j, queue, visited);
dfs( A, i+1, j, queue, visited);
dfs( A, i, j-1, queue, visited);
dfs( A, i, j+1, queue, visited);
}
}
这个题综合考察了 dfs 和 bfs，是一个很经典的好题。
相信通过深入理解此题，会对进一步领悟 dfs 和 bfs有更好的帮助。
那今天就先到这里啦，下节见~
