题目如下：

In a given 2D binary array A, there are two islands.  (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped.  (It is guaranteed that the answer is at least 1.)

 

Example 1:

Input: [[0,1],[1,0]]Output: 1

Example 2:

Input: [[0,1,0],[0,0,0],[0,0,1]]Output: 2

Example 3:

Input: [[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]]Output: 1

 Note:

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

解题思路：典型的DFS/BFS场景。题目中约定了只存在两个岛，所以先用DFS/BFS找出第一个岛的所有坐标，并把Input中属于第一个岛的元素值标记成2。接下来再对值为2的元素做DFS/BFS，找出与元素1最近的距离，这个距离就是结果。

代码如下：

class Solution(object):    def getOneIsland(self,visit,A):        for i in range(len(A)):            for j in range(len(A[i])):                if A[i][j] == 0:                    continue                q = [(i,j)]                visit[i][j] = 1                A[i][j] = 2                while len(q) > 0:                    x,y = q.pop(0)                    if x - 1 >= 0 and A[x - 1][y] == 1 and visit[x - 1][y] == 0:                        visit[x - 1][y] = 1                        A[x - 1][y] = 2                        q.append((x - 1, y))                    if y - 1 >= 0 and A[x][y - 1] == 1 and visit[x][y - 1] == 0:                        visit[x][y - 1] = 1                        A[x][y - 1] = 2                        q.append((x, y - 1))                    if x + 1 < len(A) and A[x + 1][y] == 1 and visit[x + 1][y] == 0:                        visit[x + 1][y] = 1                        A[x + 1][y] = 2                        q.append((x + 1, y))                    if y + 1 < len(A[0]) and A[x][y + 1] == 1 and visit[x][y + 1] == 0:                        visit[x][y + 1] = 1                        A[x][y + 1] = 2                        q.append((x, y + 1))                return    def shortestBridge(self, A):        """        :type A: List[List[int]]        :rtype: int        """        visit = []        for i in A:            tl = [0] * len(i)            visit.append(tl)        res = 10000        self.getOneIsland(visit,A)        for i in range(len(A)):            for j in range(len(A[i])):                if A[i][j] != 2:                    continue                q = [(i,j,0)]                while len(q) > 0:                    x,y,z = q.pop(0)                    if z > res:                        continue                    if x - 1 >= 0 and A[x - 1][y] == 1:                        res = min(res,z)                    if y - 1 >= 0 and A[x][y - 1] == 1:                        res = min(res, z)                    if x + 1 < len(A) and A[x + 1][y] == 1:                        res = min(res, z)                    if y + 1 < len(A[0]) and A[x][y + 1] == 1:                        res = min(res, z)                    if x - 1 >= 0 and A[x - 1][y] == 0 and (visit[x - 1][y] == 0 or visit[x - 1][y] > z + 1):                        visit[x - 1][y] = z+1                        q.append((x - 1, y,z+1))                    if y - 1 >= 0 and A[x][y - 1] == 0 and (visit[x][y-1] == 0 or visit[x][y - 1] > z + 1):                        visit[x][y - 1] = z+1                        q.append((x, y - 1,z+1))                    if x + 1 < len(A) and A[x + 1][y] == 0 and (visit[x+1][y] == 0 or visit[x + 1][y] > z + 1):                        visit[x + 1][y] = z+1                        q.append((x + 1, y,z+1))                    if y + 1 < len(A[0]) and A[x][y + 1] == 0 and (visit[x][y+1] == 0 or visit[x][y + 1] > z + 1):                        visit[x][y + 1] = z+1                        q.append((x, y + 1,z+1))        return res