Walls and Gates 07/30
Example
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF 3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4public class Solution {
/**
* @param rooms: m x n 2D grid
* @return: nothing
*/
public void wallsAndGates(int[][] rooms) {
// write your code here
int n = rooms.length;
if(n == 0){
return;
}
int m = rooms[0].length;
//用来找到一个点的上下左右点
int[] dx= {1,0,-1,0};
int[] dy = {0,1,0,-1};
Queue<Integer> qx = new LinkedList<>();
Queue<Integer> qy = new LinkedList<>();
for (int i =0;i < n ;i++ ){
for(int j = 0; j < m; j++){
if(rooms[i][j] == 0){
qx.offer(i);
qy.offer(j);
}
}
}
while(!qx.isEmpty()){
int cx = qx.poll();
int cy = qy.poll();
for(int i = 0; i < 4; ++i){
int nx = cx+dx[i];
int ny = cy + dy[i];
if(nx < n && nx >= 0 && ny < m && ny >= 0 && rooms[nx][ny] == Integer.MAX_VALUE){
qx.offer(nx);
qy.offer(ny);
rooms[nx][ny] = rooms[cx][cy]+1;
}
}
}
}
}Last updated