803. Bricks Falling When Hit

写了好久
自己想不到
重点是倒着加点的时候，如果这个点不是connect to top, 就不进行count
因为不connect to top, 证明了这个点是之前的点remove的时候掉下去的！

Version #2 Union Find[TODO]

Version #1 DFS
79.69 %

class Solution {
    public int[] hitBricks(int[][] grid, int[][] hits) {
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0 || hits == null) {
return new int[0];
}
int rows = grid.length;
int cols = grid[0].length;
int[] result = new int[hits.length];
for (int[] hit : hits) {
if (grid[hit[0]][hit[1]] == 1) {
grid[hit[0]][hit[1]] = -1;
}
}
         
for (int x = 0; x < cols; x++) {
if (grid[0][x] == 1) {
dfs(0, x, grid);
}
}

for (int i = hits.length - 1; i >= 0; i--) {
int[] count = new int[1];
if (grid[hits[i][0]][hits[i][1]] == -1) {
                    grid[hits[i][0]][hits[i][1]] = 1;
                    if (connectedToTop(hits[i][0], hits[i][1], grid)) {
                        search(hits[i][0], hits[i][1], grid, count);
                    }
}
result[i] = count[0] == 0 ? 0 : (count[0] - 1);
}
return result;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
// mark all nodes connect to top as 2
private void dfs(int y, int x, int[][] grid) {
grid[y][x] = 2; // visited
for (int i = 0; i < 4; i++) {
int currX = x + dx[i];
int currY = y + dy[i];
if (currX >= 0 && currY >= 0 && currX < grid[0].length && currY < grid.length && grid[currY][currX] == 1) {
dfs(currY, currX, grid);
}
}
}

    /*
    0 2
    1 -1
    2 2
    3 -1
    4 -1
    */
 
    private boolean connectedToTop(int y, int x, int[][] grid) {
        if (y == 0) {
            return true;
        }
        for (int i = 0; i < 4; i++) {
int currX = x + dx[i];
int currY = y + dy[i];
if (currX >= 0 && currY >= 0 && currX < grid[0].length && currY < grid.length
               && grid[currY][currX] == 2) {
                return true;
}
}
        return false;
    }
 
private void search(int y, int x, int[][] grid, int[] count) {
     
grid[y][x] = 2; // visited
count[0]++;
        for (int i = 0; i < 4; i++) {
int currX = x + dx[i];
int currY = y + dy[i];
if (currX >= 0 && currY >= 0 && currX < grid[0].length && currY < grid.length && grid[currY][currX] == 1) {
search(currY, currX, grid, count);
}
}
}
}