# 0286. Walls and Gates
###### tags: `Leetcode` `Medium` `BFS`
Link: https://leetcode.com/problems/walls-and-gates/
## 思路
BFS
但是很巧妙的一点是这次BFS在开头的时候把所有的gate都加进去
这样算出的结果都是最短距离
（不需要用层序遍历，因为每个neighbor的值都是curr pos的值+1，已经是层序遍历了~）
## Code

class Solution {
    private static final int EMPTY = Integer.MAX_VALUE;
    private static final int GATE = 0;
    private static final int[][] directions = new int[][] {{-1,0},{1,0},{0,-1},{0,1}};
    public void wallsAndGates(int[][] rooms) {
        Queue<int[]> q = new LinkedList<>();
        for(int i = 0;i < rooms.length;i++){
            for(int j = 0;j < rooms[0].length;j++){
                if(rooms[i][j] == GATE){
                    q.add(new int[]{i,j});
                }
            }
        }
        
        while(!q.isEmpty()){
            int[] curr = q.poll();
            List<int[]> nextPos = getNext(curr, rooms.length, rooms[0].length, rooms);
            for(int[] next:nextPos){
                rooms[next[0]][next[1]] = rooms[curr[0]][curr[1]]+1;
                q.add(next);
            }
        }
        return;
    }
    public List<int[]> getNext(int[] curr, int m, int n, int[][] rooms){
        List<int[]> res = new ArrayList<>();
        for(int i = 0;i < directions.length;i++){
            int newRow = curr[0]+directions[i][0];
            int newCol = curr[1]+directions[i][1];
            if(newRow<0 || newRow>=m || newCol<0 || newCol>=n || rooms[newRow][newCol]!=EMPTY){}
            else{
                res.add(new int[]{newRow, newCol});
            }
        }
        return res;
    }
}