// 耗时7ms

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

if (rooms.length == 0) {

return;

}

int row = rooms.length, col = rooms[0].length;

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

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

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

dfs(rooms, i, j, 0);

}

}

}

}

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

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

return;

}

// 这个条件非常重要

// 如果rooms[i][j]=0,dis=0，则这里可以继续走下去

// 如果rooms[i][j]=0,dis!=0，则这里直接跳过，表示遇到另一个0了，那个门的情况我们不处理

// 如果room[i][j]!=0,dis!=0,但是rooms[i][j]<dis，有两种情况，

// 1. 一种是在当前dfs中该节点被访问过了，所以值会比dis小，这种情况下就别重复访问了

// 2. 另一种是当前dfs没访问过，但是在另一个dfs中访问过了，该节点离另一个门比较近，所以这个节点会绕过，虽然这个节点

// 的邻居节点本次没有访问，但是仍然会通过其他的路径访问到的，所以这里直接return没有影响。

if (rooms[i][j] < dis) {

return;

}

rooms[i][j] = dis;

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

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

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

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

}

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

if (rooms.length == 0) {

return;

}

int row = rooms.length, col = rooms[0].length;

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

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

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

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

queue.add(new int[] {i, j});

}

}

}

int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

while (!queue.isEmpty()) {

int[] pos = queue.poll();

int x = pos[0], y = pos[1];

for (int i = 0; i < dx.length; i++) {

int x0 = x + dx[i], y0 = y + dy[i];

/**

if (x0 >= 0 && x0 < rooms.length && y0 >= 0 && y0 < rooms[0].length && rooms[x0][y0] == Integer.MAX_VALUE) {

rooms[x0][y0] = rooms[x][y] + 1;

queue.add(new int[] {x0, y0});

}

}

}

}