You are given an m x n binary grid, where each 1 represents a brick and 0 represents an empty space. A brick is stable if:


	It is directly connected to the top of the grid, or
	At least one other brick in its four adjacent cells is stable.


You are also given an array hits, which is a sequence of erasures we want to apply. Each time we want to erase the brick at the location hits[i] = (rowi, coli). The brick on that location&nbsp;(if it exists) will disappear. Some other bricks may no longer be stable because of that erasure and will fall. Once a brick falls, it is immediately erased from the grid (i.e., it does not land on other stable bricks).

Return an array result, where each result[i] is the number of bricks that will fall after the ith erasure is applied.

Note that an erasure may refer to a location with no brick, and if it does, no bricks drop.

&nbsp;
Example 1:

Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
Output: [2]
Explanation: Starting with the grid:
[[1,0,0,0],
 [1,1,1,0]]
We erase the underlined brick at (1,0), resulting in the grid:
[[1,0,0,0],
 [0,1,1,0]]
The two underlined bricks are no longer stable as they are no longer connected to the top nor adjacent to another stable brick, so they will fall. The resulting grid is:
[[1,0,0,0],
 [0,0,0,0]]
Hence the result is [2].


Example 2:

Input: grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
Output: [0,0]
Explanation: Starting with the grid:
[[1,0,0,0],
 [1,1,0,0]]
We erase the underlined brick at (1,1), resulting in the grid:
[[1,0,0,0],
 [1,0,0,0]]
All remaining bricks are still stable, so no bricks fall. The grid remains the same:
[[1,0,0,0],
 [1,0,0,0]]
Next, we erase the underlined brick at (1,0), resulting in the grid:
[[1,0,0,0],
 [0,0,0,0]]
Once again, all remaining bricks are still stable, so no bricks fall.
Hence the result is [0,0].


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 200
	grid[i][j] is 0 or 1.
	1 &lt;= hits.length &lt;= 4 * 104
	hits[i].length == 2
	0 &lt;= xi&nbsp;&lt;= m - 1
	0 &lt;=&nbsp;yi &lt;= n - 1
	All (xi, yi) are unique.


from collections import defaultdict

class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        parent = defaultdict()
        sz = defaultdict(lambda:1)
        empty = set()
        def find(i):
            if parent[i] != i:
                parent[i] = find(parent[i])
            return parent[i]
        def union(i,j):
            pi = find(i)
            pj = find(j)
            if pi != pj:
                parent[pi] = pj
                sz[pj] += sz[pi]
        row = len(grid)
        col = len(grid[0])
        for r in range(row):
            for c in range(col):
                parent[(r,c)] = (r,c)
        parent[(row,col)] = (row,col)
        for r, c in hits:
            if grid[r][c]:
                grid[r][c] = 0
            else:
                empty.add((r,c))
        for r in range(row):
            for c in range(col):
                if not grid[r][c]:
                    continue
                for dr, dc in [[-1,0],[1,0],[0,1],[0,-1]]:
                    if 0 <= r + dr < row and 0 <= c + dc < col and grid[r+dr][c+dc]:
                        union((r, c),(r+dr, c+dc))
                if r == 0:
                    union((r,c),(row,col))
        res = [0]*len(hits)
        for i in range(len(hits)-1,-1,-1):
            r, c = hits[i]
            if (r,c) in empty:
                continue
            grid[r][c] = 1
            curbricks = sz[find((row,col))]
            for dr, dc in [[-1,0],[1,0],[0,1],[0,-1]]:
                if 0 <= r + dr < row and 0 <= c + dc < col and grid[r+dr][c+dc]:
                    union((r,c),(r+dr,c+dc))
            if r == 0:
                union((r,c),(row,col))
            nextbricks = sz[find((row,col))]
            if nextbricks > curbricks:
                res[i] = nextbricks - curbricks - 1
        return res
class Solution {
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};

    public int[] hitBricks(int[][] grid, int[][] hits) {
        //marking all the hits that has a brick with -1
        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;
        
        //marking all the stable bricks
        for(int i=0;i<grid[0].length;i++)
            markAndCountStableBricks(grid, 0, i);
        
        int[] res = new int[hits.length];
        //looping over hits array backwards and restoring bricks
        for(int i=hits.length-1;i>=0;i--){
            int row = hits[i][0];
            int col = hits[i][1];
            
            //hit is at empty space so continue
            if(grid[row][col] == 0)
                continue;
            
            //marking it with 1, this signifies that a brick is present in an unstable state and will be restored in the future
            grid[row][col] = 1;
            // checking brick stability, if it's unstable no need to visit the neighbours
            if(!isStable(grid, row, col))
                continue;
			
			//So now as our brick is stable we can restore all the bricks connected to it
            //mark all the unstable bricks as stable and get the count
            res[i] = markAndCountStableBricks(grid, hits[i][0], hits[i][1])-1; //Subtracting 1 from the total count, as we don't wanna include the starting restored brick
        }
        
        return res;
    }
    
    private int markAndCountStableBricks(int[][] grid, int row, int col){
        if(grid[row][col] == 0 || grid[row][col] == -1)
            return 0;
        
        grid[row][col] = 2;
        int stableBricks = 1;
        for(int[] dir:dirs){
            int r = row+dir[0];
            int c = col+dir[1];
            
            if(r < 0 || r >= grid.length || c < 0 || c >= grid[0].length)
                continue;
            
            if(grid[r][c] == 0 || grid[r][c] == -1 || grid[r][c] == 2)
                continue;
            
            stableBricks += markAndCountStableBricks(grid, r, c);
        }
        
        return stableBricks;
    }
    
    private boolean isStable(int[][] grid, int row, int col){
        if(row == 0)
            return true;
        
        for(int[] dir:dirs){
            int r = row+dir[0];
            int c = col+dir[1];
            
            if(r < 0 || r >= grid.length || c < 0 || c >= grid[0].length)
                continue;
            
            if(grid[r][c] == 2)
                return true;
        }
        
        return false;
    }
}
class Solution {
public:
	// Helper function to determine if the passed node is connected to the top of the matrix
    bool isConnected(vector<vector<bool>>& vis, int& i, int& j){
        if(i==0)
            return true;
        
        if(i>0 && vis[i-1][j])
            return true;
        if(j>0 && vis[i][j-1])
            return true;
        if(i<vis.size()-1 && vis[i+1][j])
            return true;
        if(j<vis[0].size()-1 && vis[i][j+1])
            return true;
        
        return false;
    }
    
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        vector<int> ans(hits.size(), 0);
        
		//Remove all the bricks which are hit during entire process
        vector<vector<int>> mat = grid;
        for(int i=0; i<hits.size(); i++)
            mat[hits[i][0]][hits[i][1]] = 0;
        
		//Do BFS to determine connected nodes (to top of matrix) and mark them as visited
        vector<vector<bool>> vis(grid.size(), vector<bool> (grid[0].size(), false));
        queue<pair<int, int>> q;
        for(int i=0; i<grid[0].size(); i++){
            if(mat[0][i]==1){
                vis[0][i] = true;
                q.push({0, i});
            }
        }
        while(!q.empty()){
            int idx = q.front().first, jdx = q.front().second;
            q.pop();
            
            if(idx>0 && mat[idx-1][jdx]==1){
                if(!vis[idx-1][jdx])
                    q.push({idx-1, jdx});
                vis[idx-1][jdx]=true;
            }
            if(jdx>0 && mat[idx][jdx-1]==1){
                if(!vis[idx][jdx-1])
                    q.push({idx, jdx-1});
                vis[idx][jdx-1]=true;
            }
            if(idx<grid.size()-1 && mat[idx+1][jdx]==1){
                if(!vis[idx+1][jdx])
                    q.push({idx+1, jdx});
                vis[idx+1][jdx]=true;
            }
            if(jdx<grid[0].size()-1 && mat[idx][jdx+1]==1){
                if(!vis[idx][jdx+1])
                    q.push({idx, jdx+1});
                vis[idx][jdx+1]=true;
            }
        }
        
        //Traverse the hits array in reverse order to one by one add a brick 
        for(int i=hits.size()-1; i>=0; i--){
			//If no brick was present in original grid matrix, continue, otherwise 
			//add brick to that position
            if(grid[hits[i][0]][hits[i][1]]==0)
                continue;
            mat[hits[i][0]][hits[i][1]] = 1;
            
			//If this brick not connected to top of matrix, ans=0 and continue
            if(!isConnected(vis, hits[i][0], hits[i][1]))
                continue;
            
			//This brick connects between visited nodes and not visited nodes, do BFS
			//to make all reachable nodes visited and count them
            q.push({hits[i][0], hits[i][1]});
            vis[hits[i][0]][hits[i][1]] = true;
            int cnt=0;
            while(!q.empty()){
                int idx = q.front().first, jdx = q.front().second;
                q.pop();
                cnt++;
                if(idx>0 && mat[idx-1][jdx]==1 && !vis[idx-1][jdx]){
                    q.push({idx-1, jdx});
                    vis[idx-1][jdx]=true;
                }
                if(jdx>0 && mat[idx][jdx-1]==1 && !vis[idx][jdx-1]){
                    q.push({idx, jdx-1});
                    vis[idx][jdx-1]=true;
                }
                if(idx<grid.size()-1 && mat[idx+1][jdx]==1 && !vis[idx+1][jdx]){
                    q.push({idx+1, jdx});
                    vis[idx+1][jdx]=true;
                }
                if(jdx<grid[0].size()-1 && mat[idx][jdx+1]==1 && !vis[idx][jdx+1]){
                    q.push({idx, jdx+1});
                    vis[idx][jdx+1]=true;
                }
            }
            ans[i] = cnt-1;
        }
        return ans;
    }
};
 var hitBricks = function(grid, hits) {
    let output = []
    for (let i = 0; i < hits.length; i++) {
        let map = {};
        
        if (grid[hits[i][0]][hits[i][1]] == 1) {
            
            grid[hits[i][0]][hits[i][1]] = 0;
            
            
            for (let j = 0; j<grid[0].length; j++) {
                if (grid[0][j] == 1) {
                    dfs (grid, output, map, 0, j);
                    break;
                }
            }
            /* removing bricks that are not connected and adding the count to array */
            removeBricks(grid, map, output);  
        } else {
            output.push(0)
        }
        
        
    }
    return output;
};

function dfs(grid, output, map, i, j) {
    
    if (i >= grid.length || j >= grid[0].length || i < 0 || j < 0) return;
    
    let key = i +'_'+ j
    
    if (map[key]) return;
    
    if (grid[i][j] == 1) {
        
        map[key] = 1;
        
        dfs(grid, output, map, i+1, j);
        dfs(grid, output, map, i-1, j);
        dfs(grid, output, map, i, j+1);
        dfs(grid, output, map, i, j-1);
        
    }
    
}

function removeBricks (grid, map, output) {
    let count = 0;
    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < grid[row].length; col++) {
            let key = row +'_'+ col;
            
            if (grid[row][col] == 1 && !map[key] ) {
                grid[row][col] = 0;
                count++
            }
        }
    }
    output.push(count)
    
}
Bricks Falling When Hit