Python | LeetCode

Задача: 934. Shortest Bridge Сложность: 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)

Ставь 👍 и забирай 📚 Базу знаний