class Solution {
    public int[] hitBricks(int[][] grid, int[][] hits) {
        int[] ans = new int[hits.length];
        int index = 0;
        //remove hits reversely
        for (int i = 0; i < hits.length; i++) {
            if (grid[hits[i][0]][hits[i][1]] == 1) {
                grid[hits[i][0]][hits[i][1]] = -1;
            }
        }
        //dfs top
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[0][j] == 1) {
                 dfs(grid, 0, j);
            } 
        }
        //count each hits
        for (int i = hits.length - 1; i >= 0; i--) {
            int ii = hits[i][0];
            int jj = hits[i][1];
            //System.out.println(ii +"-"+jj+"-"+grid[ii][jj]);
            if (grid[ii][jj] == -1 && 
                    (ii-1 < 0 || grid[ii - 1][jj] == 2 || 
                     ii + 1 < grid.length && grid[ii + 1][jj] == 2 ||
                     jj + 1 < grid[0].length && grid[ii][jj + 1] == 2 ||
                     jj - 1 >= 0 && grid[ii][jj - 1] == 2 )) {
                    grid[ii][jj] = 1;
                    ans[index++] = count(grid, ii, jj) - 1;
            } else if (grid[ii][jj] == -1){
                grid[ii][jj] = 1;
                ans[index++] = 0;
            } else {

                ans[index++] = 0;
            }
        }
        for (int i = 0; i < ans.length/2; i++) {
            int tmp = ans[i];
            ans[i] = ans[ans.length - i - 1];
            ans[ans.length - i - 1] = tmp;
        }
        return ans;

    }
    private void dfs(int[][] grid, int i, int j) {
        //System.out.print(i+""+j);
        if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1){
            grid[i][j] = 2;
        } else {
            return;
        }

        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
    private int count(int[][] grid, int i, int j) {
        if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1 ){
            grid[i][j] = 2;
        }else {
            return 0;
        }

        return 1 + count(grid, i - 1, j) + count(grid, i + 1, j) +count(grid, i, j - 1) + count(grid, i, j + 1);


    }
}