Leetcode 934. Разбор задачи на Python с использованием dfs + bfs

Разбираем задачу с сайта Leetcode на языке программирования Python. Решение оказалось лучше 70% всех предложенных пользователями.

4746

Всем привет. Сегодня попробую объяснить моё решение задачи с сайта Leetcode на языке программирования Python.

Формулировка задачи (мой перевод):

Вам дана двоичная матрица размера n x n, где 1 представляет сушу, а 0 представляет воду.

Остров — это 4-направленно связанная группа 1, не связанная ни с какими другими 1. В сетке ровно два острова.

Вы можете изменить 0 на 1, чтобы соединить два острова в один остров.

Возвращает наименьшее количество нулей, которое нужно перевернуть, чтобы соединить два острова.

Официальная формулировка задачи:

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])

4746