Сложность: medium
Вам дана двоичная матричная сетка n x n, где 1 обозначает сушу, а 0 - воду. Остров - это 4-направленно связанная группа из 1, не соединенная ни с одной другой 1. В сетке ровно два острова. Вы можете поменять 0 на 1, чтобы соединить два острова в один. Верните наименьшее количество 0, которое нужно перевернуть, чтобы соединить два острова.
Пример:
Input: grid = [[0,1],[1,0]]
Output: 1
👨💻 Алгоритм:
1⃣Найти все клетки, принадлежащие первому острову, используя DFS/BFS, и добавить их в очередь для последующего расширения.
2⃣Использовать BFS для расширения из каждой клетки первого острова, чтобы найти кратчайший путь к клетке второго острова.
3⃣Вернуть длину кратчайшего пути.
😎 Решение:
from collections import deque
def shortestBridge(grid):
n = len(grid)
def neighbors(x, y):
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
if 0 <= x + dx < n and 0 <= y + dy < n:
yield x + dx, y + dy
def bfs(queue):
visited = set(queue)
steps = 0
while queue:
new_queue = []
for x, y in queue:
for nx, ny in neighbors(x, y):
if (nx, ny) not in visited:
if grid[nx][ny] == 1:
return steps
visited.add((nx, ny))
new_queue.append((nx, ny))
queue = new_queue
steps += 1
def find_first_island():
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
queue = deque([(i, j)])
grid[i][j] = -1
island = [(i, j)]
while queue:
x, y = queue.popleft()
for nx, ny in neighbors(x, y):
if grid[nx][ny] == 1:
grid[nx][ny] = -1
queue.append((nx, ny))
island.append((nx, ny))
return island
island = find_first_island()
return bfs(island)
Ставь 👍 и забирай 📚 Базу знаний