共计 1383 个字符，预计需要花费 4 分钟才能阅读完成。
题目地址：https://leetcode-cn.com/probl… 题目描述：在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）
现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。
返回必须翻转的 0 的最小数目。（可以保证答案至少是 1。）
解答：题的意思就是说，有两片岛屿，岛屿是指联通的 1 组成的区域，求这两片岛屿之间的最短距离。思路是这样的，用图的深度优先搜索 dfs 算法，来找出第一个岛屿里的全部点，加入 list1，然后同样的方法找到第二个岛屿的全部点，加入 list2，然后求 list1 中任意一点到 list2 中任意一点距离的最小值即可，这里的距离是指 abs(x1-x2)+abs(y1-y2)-1abs 为绝对值，x1，y1 为 list1 的某点的坐标，x2，y2 为 list2 的某点坐标。
java ac 代码：
class Solution {
class Node
{
int x,y;
public Node(int x,int y)
{
this.x = x;
this.y = y;
}
}
public int shortestBridge(int[][] A) {
boolean[][] visited = new boolean[A.length][A[0].length];
List<Node> l1 = new ArrayList(1000);
List<Node> l2 = new ArrayList(1000);
for(int i = 0;i < A.length;i++)
{
boolean flag = false;
for(int j = 0;j < A[0].length;j++)
if(A[i][j] == 1&&!visited[i][j]){
dfs(A,visited,i,j,l1);
flag = true;
break;
}
if(flag)break;
}
for(int i = 0;i < A.length;i++)
{
boolean flag = false;
for(int j = 0;j < A[0].length;j++)
if(A[i][j] == 1&&!visited[i][j]){
dfs(A,visited,i,j,l2);
flag = true;
break;
}
if(flag)break;
}
int ans = Integer.MAX_VALUE;
for(int i = 0;i < l1.size();i++)
for(int j = 0;j < l2.size();j++)
ans = Math.min(ans,Math.abs(l1.get(i).x-l2.get(j).x)+Math.abs(l1.get(i).y-l2.get(j).y)-1);
return ans;
}
void dfs(int[][] A,boolean[][] visited,int x,int y,List<Node> l)
{
if(!(x >= 0&&x < A.length&& y>=0 && y< A[0].length) || visited[x][y]||A[x][y] !=1 )
return;
visited[x][y] = true;
l.add(new Node(x,y));
dfs(A,visited,x-1,y,l);
dfs(A,visited,x+1,y,l);
dfs(A,visited,x,y-1,l);
dfs(A,visited,x,y+1,l);
}
}
用时 400 多 ms，如果用 python 可能会超时。
