# 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.

``````public void wallsAndGates(int[][] rooms) {
for (int i = 0; i < rooms.length; i++)
for (int j = 0; j < rooms[0].length; j++)
if (rooms[i][j] == 0)
BFS(rooms, new Point(j, i));
}

void BFS(int[][] rooms, Point cur) {
Point[] dirs = {new Point(0, 1), new Point(0, -1), new Point(1, 0), new Point(-1, 0)};// 4 directions
Queue<Point>queue = new LinkedList<Point>();
queue.offer(cur);
while (!queue.isEmpty()) {
cur = queue.poll();
for (Point d : dirs) {
if (cur.x+d.x >= 0 && cur.x+d.x < rooms[0].length && cur.y+d.y >= 0 && cur.y+d.y < rooms.length// Validate coordinates
&& 	rooms[cur.y+d.y] [cur.x+d.x]> rooms[cur.y][cur.x] + 1) {// Compare distance
rooms[cur.y+d.y] [cur.x+d.x] = rooms[cur.y][cur.x] + 1;
queue.offer(new Point(cur.x+d.x, cur.y+d.y));
}
}
}
}``````

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