1. Для начала я предлагаю найти 1-ый остров в матрице, с помощью обхода в глубину (dfs), если мы нашли элемент 1-го острова, тогда меняем значение в двумерной матрице на 2. Для экономии времени мы будем заранее заполнять очередь для будущего обхода в ширину (bfs).
n = len(grid)
queue = []
def dfs(x, y):
if x > 0 or x >= n or 0 > y or y >= n or grid[x][y] != 1:
return
grid[x][y] = 2
queue.append([x, y, 0])
dfs(x - 1, y)
dfs(x + 1, y)
dfs(x, y - 1)
dfs(x, y + 1)
# Перебираем двумерный массив, пока не найдем первый элемент суши
flag = False
for i in range(n):
for j in range(n):
if grid[i][j]:
dfs(i, j)
flag = True
break
if flag:
break
2. С помощью обхода в ширину мы найдем кратчайший путь до 2-го острова, для этого мы заполнили очередь координатами элементов 1-го острова.
# Чтобы убрать больше количество условных операторов
# я буду использовать цикл for, в котором я буду перебирать
# все возможные варианты дальнейшего пути
dirct = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while len(queue) != 0:
# step - расстояние до 2-го острова
x, y, step = queue[0][0], queue[0][1], queue[0][2]
queue.pop(0)
for dx, dy in dirct:
x1, y1 = x + dx, y + dy
if 0 > x1 or x1 >= n or 0 > y1 or y1 >= n:
continue
if grid[x1][y1] == 1:
return step # ответ на задачу
if grid[x1][y1] == 0:
grid[x1][y1] = 2
queue.append([x1, y1, step + 1])
Весь код:
class Solution(object):
def shortestBridge(self, grid):
n = len(grid)
queue = []
def dfs(x, y):
if 0 > x or x >= n or 0 > y or y >= n or grid[x][y] != 1:
return
grid[x][y] = 2
queue.append([x, y, 0])
dfs(x - 1, y)
dfs(x, y - 1)
dfs(x + 1, y)
dfs(x, y + 1)
flag = False
for i in range(n):
for j in range(n):
if grid[i][j]:
dfs(i, j)
flag = True
break
if flag:
break
dirct = [(0, 1), (1, 0), (-1, 0), (0, -1)]
while len(queue) != 0:
x, y, step = queue[0][0], queue[0][1], queue[0][2]
queue.pop(0)
for dx, dy in dirct:
x1, y1 = x + dx, y + dy
if 0 > x1 or x1 >= n or 0 > y1 or y1 >= n:
continue
if grid[x1][y1] == 1:
return step
if grid[x1][y1] == 0:
grid[x1][y1] = 2
queue.append([x1, y1, step + 1])
Энтузиаст создал GitHub-репозиторий, собравший в себе лучшие open source шаблоны для быстрого старта новых проектов. Коллекция включает готовые решения для различных технологий и платформ, таких как веб-разработка, мобильные и серверные приложения, с настроенной архитектурой, конфигурацией и инструментами
Библиотеки для работы с графами в Python. Показываем, как работать с NetworkX и Graph-tool. Рассматриваем возможные варианты и пошаговую инструкцию ✔ Tproger