# 1091. Shortest Path in Binary Matrix
###### tags: `Leetcode` `Medium` `FaceBook` `BFS`
Link: https://leetcode.com/problems/shortest-path-in-binary-matrix/
## 思路
BFS
queue里面放的都是数值为0的点，如果起点数值为1，直接return
不要只在getDirection里面检查完这个点有没有被visited过之后 在bfs的时候就不检查了，visited是有可能在中间发生变化的，如果不检查就会TLE
## Code

class Solution {
    private static final int[][] directions = new int[][] {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    public int shortestPathBinaryMatrix(int[][] grid) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int len = 1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0,0});
        if(grid[0][0] == 1) return -1;
        
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i < size;i++){
                int[] curr = q.poll();
                if(curr[0] == grid.length-1 && curr[1] == grid[0].length-1) return len;
                List<int[]> possibleDir = getDirection(curr, grid.length, grid[0].length,grid);
                for(int[] next:possibleDir){
                    if(!visited[next[0]][next[1]]){
                        visited[next[0]][next[1]] = true;
                        q.add(next);
                    }
                }   
            }
            len++;
        }
        return -1;
    }
    public List<int[]> getDirection(int[] curr, int row, int col, int[][] grid){
        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>=row || newCol<0 || newCol>=col || grid[newRow][newCol]==1){
                
            }
            else{
                res.add(new int[]{newRow, newCol});
            }
        }
        return res;
    }
}