934. Shortest Bridge 最短的桥

@TOC

# 题目描述

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

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

Return the smallest number of `0`s 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

``````class Solution:
def shortestBridge(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
M, N = len(A), len(A[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = [[0] * N for _ in range(M)]
hasfind = False
que = collections.deque()
for i in range(M):
if hasfind: break
for j in range(N):
if A[i][j] == 1:
self.dfs(A, i, j, visited, que)
hasfind = True
break
step = 0
while que:
size = len(que)
for _ in range(size):
i, j = que.popleft()
for d in dirs:
x, y = i + d[0], j + d[1]
if 0 <= x < M and 0 <= y < N:
visited[x][y] = 1
if A[x][y] == 1:
return step
elif A[x][y] == 0:
A[x][y] = 2
que.append((x, y))
else:
continue
step += 1
return -1

def dfs(self, A, i, j, visited, que):
if visited[i][j]: return
visited[i][j] = 1
M, N = len(A), len(A[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
if A[i][j] == 1:
que.append((i, j))
A[i][j] = 2
for d in dirs:
x, y = i + d[0], j + d[1]
if 0 <= x < M and 0 <= y < N:
self.dfs(A, x, y, visited, que)
``````

# 日期

2018 年 11 月 4 日 —— 下雨的周日