# ac solution code

• 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
}
}
}
}
``````

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