Walls and Gates

lc 286

You are given a m x n 2D grid initialized with these three possible values.

-1 - A wall or an obstacle. 0 - A gate. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

题意理解：当是0就是door，是－1就是wall不能走了，inf是一个空房间，两个空房间如果能通道一个门，是可以改变inf的数值的

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

    if(rooms.length==0) return;
    Queue <int[]> queue = new LinkedList<int[]>();
    int[] dx= {0,1,-1,0};
    int[] dy= {1,0,0,-1};

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

    while(!queue.isEmpty()){
        int[] door=queue.poll();
        int row= door[0];
        int col=door[1];

        for(int d = 0; d < dx.length; d++){
            //这里是bfs，都是从门这一层level开始的，所以说如果max被改掉了，那么只能是前面改掉是最大的情况，这里就使运算加快了，我酸的时候就忽略了这个，所以tle了
            if(row + dy[d] >= 0 && row+dy[d] < rooms.length && col+dx[d]>=0 && col+dx[d]< rooms[0].length && rooms[row+dy[d]][col+dx[d]] == Integer.MAX_VALUE){
                rooms[row+dy[d]][col+dx[d]]=rooms[row][col]+1;
                queue.offer(new int[]{row+dy[d],col+dx[d]});
            }
        }
    }
}}