# BFS Java with explanation

1. find the gate first
2. use BFS to find INF, no need to consider 0, -1, or other numbers
``````class Pair{
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}

public class Solution {
int[] dir = {0, 1, 0, -1, 0};

final int NUM = 4;

public void wallsAndGates(int[][] rooms) {

if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
return;
}

for (int i = 0; i < rooms.length; i++) {
for (int j = 0; j < rooms[0].length; j++) {
if (rooms[i][j] == 0) {
Pair gate = new Pair(i, j);
queue.offer(gate);
steps.offer(0);
}
}
}

while (!queue.isEmpty()) {
Pair cur = queue.poll();
int step = steps.poll();

for (int i = 0; i < NUM; i++) {
int row = cur.x + dir[i];
int col = cur.y + dir[i + 1];

if (row < 0 || row >= rooms.length || col < 0 || col >= rooms[0].length) {
continue;
}

if (rooms[row][col] == Integer.MAX_VALUE) {
rooms[row][col] = step + 1;
Pair next = new Pair(row, col);
queue.offer(next);
steps.offer(step + 1);
}

else {
continue;
}
}
}

}
}``````

• This post is deleted!

• @yixuanwang.start Yep, that is the advantage of BFS, first come first serve. Btw, you also can try int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; if you like

• This post is deleted!

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