1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| from collections import deque
class Solution(object):
def shortestBridge(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
have_find = False
first_island = deque()
for i in range(len(A)):
for j in range(len(A[0])):
if A[i][j] == 1:
self.dfs(grid=A, x=i, y=j, first_island=first_island)
have_find = True
break
if have_find:
break
distance = 2
ans = len(A) * len(A[0])
while first_island:
l = len(first_island)
for i in range(l):
x, y = first_island.popleft()
for dir_x, dir_y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
n_x, n_y = x + dir_x, y + dir_y
if self.judge(n_x, n_y, A):
if A[n_x][n_y] == 1:
ans = min(ans, abs(A[x][y]) - 1)
elif A[n_x][n_y] != 0:
A[n_x][n_y] = -1 * abs(A[n_x][n_y])
else:
A[n_x][n_y] = distance
if (n_x, n_y) not in first_island:
first_island.append((n_x, n_y))
distance += 1
return ans
def dfs(self, grid, x, y, first_island):
if x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0]):
if grid[x][y] == 1:
grid[x][y] = -1
first_island.append((x, y))
self.dfs(grid, x - 1, y, first_island)
self.dfs(grid, x + 1, y, first_island)
self.dfs(grid, x, y - 1, first_island)
self.dfs(grid, x, y + 1, first_island)
def judge(self, x, y, grid):
return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])
if __name__ == '__main__':
s = Solution()
A = [[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]]
print(s.shortestBridge(A=A))
|