private int[][] directions = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

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

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

int n = rooms.length;

int m = rooms[0].length;

for (int i=0; i<n; i++) {

for (int j=0; j<m; j++) {

if (rooms[i][j] == 0) {

for (int[] dir: directions) {

dfs(rooms, 1, i + dir[0], j + dir[1]);

}

}

}

}

}

private void dfs(int[][] rooms, int distance, int i, int j) {

if (i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length) return;

if (rooms[i][j] == -1 || rooms[i][j] == 0) return;

// can be optimized: early stop

// rooms[i][j] = Math.min(rooms[i][j], distance);

if (rooms[i][j] > distance) {

rooms[i][j] = distance;

} else if (rooms[i][j] <= distance) {

return;

}

for (int[] dir: directions) {

dfs(rooms, distance + 1, i + dir[0], j + dir[1]);

}

}

/**

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

if(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) {

dfs2(rooms, i, j, 0);

}

}

}

}

private void dfs2(int[][] rooms, int i, int j, int dis) {

if(i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || dis > rooms[i][j] || rooms[i][j] == -1) return;

rooms[i][j] = dis;

dfs2(rooms, i + 1, j, dis+1);

dfs2(rooms, i - 1, j, dis+1);

dfs2(rooms, i, j - 1, dis+1);

dfs2(rooms, i, j + 1, dis+1);

}

/**

private static final int EMPTY = Integer.MAX_VALUE;

private static final int GATE = 0;

private static final List<int[]> DIRECTIONS = Arrays.asList(

new int[] { 1, 0},

new int[] {-1, 0},

new int[] { 0, 1},

new int[] { 0, -1}

);

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

int m = rooms.length;

if (m == 0) return;

int n = rooms[0].length;

Queue<int[]> q = new LinkedList<>();

for (int row = 0; row < m; row++) {

for (int col = 0; col < n; col++) {

if (rooms[row][col] == GATE) {

q.add(new int[] { row, col });

}

}

}

while (!q.isEmpty()) {

int[] point = q.poll();

int row = point[0];

int col = point[1];

for (int[] direction : DIRECTIONS) {

int r = row + direction[0];

int c = col + direction[1];

if (r < 0 || c < 0 || r >= m || c >= n || rooms[r][c] != EMPTY) {

continue;

}

rooms[r][c] = rooms[row][col] + 1;

q.add(new int[] { r, c });

}

}

}