Shortest Bridge

Input: A = [[0,1],[1,0]]
Output: 1
Input: A = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
Input: 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]]
Output: 1
  • 2 <= A.length == A[0].length <= 100
  • A[i][j] == 0 or A[i][j] == 1
  1. 先找到第一个island的点
  2. 从第一点dfs找到boundary的值
  3. bfs, check boundary的每一个值,+1能不能够到第二个island
  4. 如果不可以,那遍历boundary外面一层所有值
def shortestBridge(self, A):
“””
:type A: List[List[int]]
:rtype: int
“””
m = len(A)
n = len(A[0])
boundary = set()
direction = [(0,1), (1,0), (-1, 0), (0, -1)]
def first():
for i in range(m):
for j in range(n):
if A[i][j] == 1:
return i, j

def dfs(i, j):
stack = set()
stack.add((i, j))
while stack:
i, j = stack.pop()
A[i][j] = -1
for d in direction:
x, y = i+d[0], j+d[1]
if 0<=x<m and 0<=y<n:
if A[x][y] == 0:
boundary.add((i,j))
elif A[x][y] == 1:
stack.add((x,y))


i ,j = first()
dfs(i, j)
step = 0

while boundary:
new = []
for i, j in boundary:
for dire in direction:
x, y = i+dire[0], j+dire[1]
if 0<=x<m and 0<=y<n:
if A[x][y] == 1:
return step
elif A[x][y] == 0:
A[x][y] = -1
new.append((x,y))
step += 1
boundary = new

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Top 10 Jquery plugins in 2020

How to Build a Vue.js Photo Gallery

‌Edit Distance

Create a Config File for Your JavaScript Project Like a Pro

Dynamic Pagination Rendering with pure JavaScript 🚀

Xamarin.Forms apps with VS Code, TypeScript and TSX

Use VS Code to develop Xamarin.Forms app with Web Atoms

A beginners guide to JavaScript Callbacks and how to avoid the Callback Hell with Promises

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Newbie Developer

Newbie Developer

More from Medium

History of Ethics and its Multicultural Origins (Part 2/2)

INTRODUCTION TO THE WORLD OF DAPPS!!

Inspirest: Introducing

Photo: Aaron Poole/NBAE via Getty Images