给出0-1二维数组，1组成两个不连通区域，为至少将几个0改为1可以让两个区域联通
BFS，先从任意1开始BFS记录所有boundary cell，然后从boundary cell开始BFS，每次处理完queue中所有元素step+1，知道搜到另一个区域
1 #934
2 #Runtime: 302 ms (Beats 92.21%)
3 #Memory: 13.9 MB (Beats 96.10%)
4
5 class Solution(object):
6 def shortestBridge(self, grid):
7 """
8 :type grid: List[List[int]]
9 :rtype: int
10 """
11 d = [[-1, 0], [1, 0], [0, 1], [0, -1]]
12 x, y = next((x, y) for x in range(len(grid)) for y in range(len(grid[0])) if grid[x][y] == 1)
13 q = deque([(x, y)])
14 boundary = set()
15 while q:
16 x, y = q.popleft()
17 grid[x][y] = -1
18 for i, j in d:
19 tx = x + i
20 ty = y + j
21 if 0 <= tx < len(grid) and 0 <= ty < len(grid[0]) and grid[tx][ty] != -1:
22 if grid[tx][ty] == 1:
23 grid[tx][ty] = -1
24 q.append((tx, ty))
25 else:
26 boundary.add((x, y))
27
28 step = 0
29 q = deque(boundary)
30 while q:
31 sz = len(q)
32 while sz > 0:
33 sz -= 1
34 x, y = q.popleft()
35 grid[x][y] = -1
36 for i, j in d:
37 tx = x + i
38 ty = y + j
39 if 0 <= tx < len(grid) and 0 <= ty < len(grid[0]) and grid[tx][ty] != -1:
40 if grid[tx][ty] == 1:
41 return step
42 else:
43 grid[tx][ty] = -1
44 q.append((tx, ty))
45 step += 1
46 return -1
47