Skip to content

Bricks Falling When Hit⚓︎

Link

Description⚓︎

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] = (row_i, col_i). The brick on that location (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 i-th erasure is applied.

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

Example 1:

  • Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
  • Output: [2]
  • Explanation:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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].

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • grid[i][j] is 0 or 1.
  • 1 <= hits.length <= 4 * 10^4
  • hits[i].length == 2
  • 0 <= x_i <= m - 1
  • 0 <= y_i <= n - 1
  • All (x_i, y_i) are unique.

Solution⚓︎

See reference.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
private:
    int m, n;

    // start from (x, y), meet 1 => infect into 2
    // return the number of newly added 2s
    int dfs(vector<vector<int>>& grid, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 1)
            return 0;
        grid[x][y] = 2;
        return 1 + dfs(grid, x + 1, y) + dfs(grid, x, y + 1) + dfs(grid, x - 1, y) + dfs(grid, x, y- 1);
    }

    bool worth(vector<vector<int>>& grid, int i, int j) {
        if (grid[i][j] != 1) return false;
        if (i == 0) return true;
        return (i > 0 && grid[i - 1][j] == 2) || (i < m - 1 && grid[i + 1][j] == 2) || (j > 0 && grid[i][j - 1] == 2) || (j < n - 1 && grid[i][j + 1] == 2);
    }

public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        m = grid.size(); n = grid[0].size();
        vector<int> res(hits.size(), 0);
        if (m == 1) return res;

        for (auto hit : hits) {
            grid[hit[0]][hit[1]]--;
        }

        for (int i = 0; i < n; i++) {
            dfs(grid, 0, i);
        }

        int row, col;
        for (int i = hits.size() - 1; i >= 0; i--) {
            row = hits[i][0]; col = hits[i][1];
            grid[row][col]++;
            if (worth(grid, row, col)) {
                res[i] = dfs(grid, row, col) - 1;
            }
        }

        return res;
    }
};

Algorithm Steps:

  1. Initialize:
  2. Store the dimensions of the grid in m and n.
  3. Create a result vector res with the same size as the number of hits, initialized to 0.
  4. Preprocessing - Marking Hits:
  5. Iterate over each hit and decrement the value in the grid at the hit location. This marks potential bricks to be removed.
  6. First DFS Pass:
  7. Perform DFS from the top row of the grid. This pass marks all bricks that are stable after the initial hits (those connected to the top row).
  8. Processing Hits in Reverse:
  9. Iterate through the hits in reverse order.
  10. For each hit, increment the grid value at the hit location (undo the hit).
  11. Check if this brick is worth considering using the worth function.
  12. If it is, perform DFS from this brick. The DFS will mark newly connected bricks as stable.
  13. The result for each hit is the number of bricks made stable by this hit minus one (the hit brick itself).
  14. Return Result:
  15. After processing all hits, return the res vector.

Code with comments:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
private:
    int m, n;  // Store the dimensions of the grid.

    // DFS function to mark and count stable bricks
    int dfs(vector<vector<int>>& grid, int x, int y) {
        // Base case: check boundaries and if the cell is not a brick (1)
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 1)
            return 0;

        // Mark the brick as part of a stable structure (2)
        grid[x][y] = 2;

        // Recursively check all four adjacent cells and count stable bricks
        return 1 + dfs(grid, x + 1, y) + dfs(grid, x, y + 1) + dfs(grid, x - 1, y) + dfs(grid, x, y - 1);
    }

    // Function to check if hitting a brick at (i, j) affects stability
    bool worth(vector<vector<int>>& grid, int i, int j) {
        // If it's not a brick or if it's on the top row, it's not worth considering
        if (grid[i][j] != 1) return false;
        if (i == 0) return true;  // Brick on the top row is always worth considering

        // Check if the brick is adjacent to any stable brick
        return (i > 0 && grid[i - 1][j] == 2) || (i < m - 1 && grid[i + 1][j] == 2) || 
               (j > 0 && grid[i][j - 1] == 2) || (j < n - 1 && grid[i][j + 1] == 2);
    }

public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        m = grid.size(); n = grid[0].size();  // Initialize grid dimensions
        vector<int> res(hits.size(), 0);      // Initialize the result vector

        // Mark the bricks to be removed due to hits
        for (auto hit : hits) {
            grid[hit[0]][hit[1]]--;
        }

        // Perform DFS from the top row to find stable bricks after all hits
        for (int i = 0; i < n; i++) {
            dfs(grid, 0, i);
        }

        // Iterate over hits in reverse to simulate each hit
        int row, col;
        for (int i = hits.size() - 1; i >= 0; i--) {
            row = hits[i][0]; col = hits[i][1];
            grid[row][col]++;  // Undo the hit

            // Check if the hit affects stability and perform DFS if it does
            if (worth(grid, row, col)) {
                res[i] = dfs(grid, row, col) - 1;  // Subtract 1 to exclude the hit brick itself
            }
        }

        // Return the result vector
        return res;
    }
};