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

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. 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.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INFINF INF INF  -1INF  -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   将 gate 做dfs 或者存入queue

public void wallsAndGates(int[][] rooms) {        for(int i = 0; i< rooms.length; i++){            for(int j = 0; j < rooms[0].length; j ++){                if(rooms[i][j] == 0)                    dfs(rooms, i, j, 0);            }        }    }    public void dfs(int[][] rooms, int i , int j, int deep){        rooms[i][j] = deep;        if(i < rooms.length - 1 && rooms[i+1][j] > deep)            dfs(rooms, i + 1, j, deep +1);                if(j < rooms[0].length - 1 && rooms[i][j + 1] > deep)           dfs(rooms, i, j + 1, deep +1);       if(j > 0 && rooms[i][j - 1] > deep)            dfs(rooms, i, j - 1, deep +1);               if(i > 0 && rooms[i-1][j] > deep)            dfs(rooms, i - 1, j, deep +1);    }

BFS

class Node{    int x;    int y;    public Node(int x, int y){        this.x = x;        this.y = y;    }}private  int inf = Integer.MAX_VALUE;    public  void wallsAndGates(int[][] nums){        Queue
     
       queue = new LinkedList<>();        for(int i = 0 ; i < nums.length; i++){            for(int j = 0; j < nums[0].length; j ++){                if(nums[i][j] == 0){                    Node x = new Node(i,j);                    queue.add(x);                }            }        }        bfs(queue, nums);    }    public  void bfs(Queue
      
        queue, int[][] nums){        while(!queue.isEmpty()){            Node root = queue.poll();            int x = root.x;            int y = root.y;            if(x < nums.length - 1 && nums[x+1][y] == inf){                nums[x+1][y] = nums[x][y] + 1;                queue.add(new Node(x+1,y));            }            if(x > 0 && nums[x-1][y] == inf){                nums[x-1][y] = nums[x][y] + 1;                queue.add(new Node(x-1,y));            }            if(y < nums[0].length - 1 && nums[x][y+1] == inf){                nums[x][y+1] = nums[x][y] + 1;                queue.add(new Node(x,y+1));            }            if(y > 0 && nums[x][y-1] == inf){                nums[x][y-1] = nums[x][y] + 1;                queue.add(new Node(x,y-1));            }        }    }}