class Solution {
    int[][] dirs = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1, -1}, {1, 0} , {1,1}};
    public int shortestPathBinaryMatrix(int[][] grid) {
        //bfs
        int m = grid.length;
        if (m == 1) return grid[0][0] == 0 ? 1 : -1; //1x1 edge case
        if (grid[0][0] == 1) return -1; //invalid start
        Queue<int[]> q = new ArrayDeque<>();
        grid[0][0] = 1; //mark visited
        q.offer(new int[] {0,0});
        HashMap<Integer,Integer> parent = new HashMap<>();
        int level = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i =0; i < size ;i++) {
                int[] cur = q.poll();
                for (int[] d : dirs) {
                    int x = d[0] + cur[0];
                    int y = d[1] + cur[1];
                    if (x >= 0 && x < m && y >= 0 && y < m && grid[x][y] == 0) {
                        parent.put(x*1000+y, cur[0] *1000 + cur[1]);
                        if (x == m-1 && y == m-1) {
                            outputPath(x*1000+y, parent);
                            return level + 1;
                        }
                        grid[x][y] = 1;//mark visited
                        q.offer(new int[] {x,y});
                    }
                }
            }
            level++;
        }
        return -1;
    }
    void outputPath(int key, HashMap<Integer,Integer> map) {
        StringBuilder sb = new StringBuilder();
        List<String> path = new ArrayList<>();
        while (map.containsKey(key)) {
            sb.append("[")
            .append(key/1000)
            .append(",")
            .append(key%1000)
            .append("]");
            path.add(sb.toString());
            sb.setLength(0);
            key = map.get(key);
        }
        path.add("[0,0]");
        Collections.reverse(path);
        System.out.println(String.join("->", path));
    }