Swift | 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⃣Вернуть длину кратчайшего пути.

😎

Решение:

class Solution {
    func shortestBridge(_ grid: [[Int]]) -> Int {
        let n = grid.count
        var grid = grid
        
        func neighbors(_ x: Int, _ y: Int) -> [(Int, Int)] {
            return [(-1, 0), (1, 0), (0, -1), (0, 1)].map { (dx, dy) in (x + dx, y + dy) }.filter { (nx, ny) in 0 <= nx && nx < n && 0 <= ny && ny < n }
        }
        
        func bfs(_ queue: [(Int, Int)]) -> Int {
            var queue = queue
            var visited = Set(queue)
            var steps = 0
            while !queue.isEmpty {
                var newQueue = [(Int, Int)]()
                for (x, y) in queue {
                    for (nx, ny) in neighbors(x, y) {
                        if !visited.contains((nx, ny)) {
                            if grid[nx][ny] == 1 {
                                return steps
                            }
                            visited.insert((nx, ny))
                            newQueue.append((nx, ny))
                        }
                    }
                }
                queue = newQueue
                steps += 1
            }
            return -1
        }
        
        func findFirstIsland() -> [(Int, Int)] {
            for i in 0..<n {
                for j in 0..<n {
                    if grid[i][j] == 1 {
                        var queue = [(i, j)]
                        grid[i][j] = -1
                        var island = [(i, j)]
                        while !queue.isEmpty {
                            let (x, y) = queue.removeFirst()
                            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
                    }
                }
            }
            return []
        }
        
        let island = findFirstIsland()
        return bfs(island)
    }
}

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

Please open Telegram to view this post