ac solution code


  • 0

    The basic idea is using BFS to start from each gate G(value=0), traversing level by level, updates all adjacent nodes if its current distance is longer than its distance from G.

    Time complexity = O(AmountOfGates * (mn)):

    For each gate, in the worst case, it will traverse all nodes in the matrix, which is mn.

        typealias Point = (x: Int, y: Int)
        func wallsAndGates(_ rooms: inout [[Int]]) {
            for i in 0 ..< rooms.count {
                for j in 0 ..< rooms[0].count {
                    if rooms[i][j] == 0 {// Found gate: traversing level by level, updates all adjacent nodes if its current distance is longer than its distance from G
                        BFS(&rooms, Point(j, i))
                    }
                }
            }
        }
        private func BFS(_ rooms: inout [[Int]], _ cur: Point) {
            let n = rooms.count, m = rooms[0].count
            let dirs: [Point] = [(0, 1), (0, -1), (1, 0), (-1, 0)] // 4 directions
            var queue = [Point]()
    
            queue.append(cur)                                           // Enqueue
            while !queue.isEmpty {
                let cur = queue.removeFirst()                           // Dequeue
                for dir in dirs {
                    if cur.x + dir.x >= 0 && cur.x + dir.x < m && cur.y + dir.y >= 0 && cur.y + dir.y < n && // Validate coordinates
                        rooms[cur.y + dir.y][cur.x + dir.x] > rooms[cur.y][cur.x] + 1 {// Compare distance: <-rooms[y][x]
                        rooms[cur.y + dir.y][cur.x + dir.x] = rooms[cur.y][cur.x] + 1
                        queue.append(Point(cur.x + dir.x, cur.y + dir.y))   // Enqueue
                    }
                }
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.