[LeetCode] 803. Bricks Falling When Hit 打击砖块掉落

2021年09月15日 阅读数:2
这篇文章主要向大家介绍[LeetCode] 803. Bricks Falling When Hit 打击砖块掉落,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

We have a grid of 1s and 0s; the 1s in a cell represent bricks.  A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.html

We will do some erasures sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may drop because of that erasure.java

Return an array representing the number of bricks that will drop after each erasure in sequence.python

Example 1:
Input: 
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
Output: [2]
Explanation: 
If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.
Example 2:
Input: 
grid = [[1,0,0,0],[1,1,0,0]]
hits = [[1,1],[1,0]]
Output: [0,0]
Explanation: 
When we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move.
So each erasure will cause no bricks dropping.
Note that the erased brick (1, 0) will not be counted as a dropped brick.

Note:app

  • The number of rows and columns in the grid will be in the range [1, 200].
  • The number of erasures will not exceed the area of the grid.
  • It is guaranteed that each erasure will be different from any other erasure, and located inside the grid.
  • An erasure may refer to a location with no brick - if it does, no bricks drop.

解法:Union Findide

Java:post

public int[] hitBricks(int[][] grid, int[][] hits) {
        int r[] = new int[hits.length], d[] = {-1, 0, 1, 0, -1};
        for (int[] h : hits)
            grid[h[0]][h[1]] -= 1;
        for (int i = 0; i < grid[0].length; i++)
            dfs(0, i, grid);
        for (int k = hits.length - 1; k >= 0; k--) {
            int h[] = hits[k], i = h[0], j = h[1];
            grid[i][j] += 1;
            if (grid[i][j] == 1 && isConnected(i, j, grid, d))
                r[k] = dfs(i, j, grid) - 1;
        }
        return r;
    }

    int dfs(int i, int j, int[][] g) {
        if (i < 0 || i >= g.length || j < 0 || j >= g[0].length || g[i][j] != 1) return 0;
        g[i][j] = 2;
        return 1 + dfs(i + 1, j, g) + dfs(i - 1, j, g) + dfs(i, j + 1, g) + dfs(i, j - 1, g);
    }

    boolean isConnected(int i, int j, int[][] g, int[] d) {
        if (i == 0) return true;
        for (int k = 1; k < d.length; k++) {
            int r = i + d[k - 1], c = j + d[k];
            if (0 <= r && r < g.length && 0 <= c && c < g[0].length && g[r][c] == 2)
                return true;
        }
        return false;
    }

Python:url

class Solution:
    def hitBricks(self, grid, hits):
        """
        :type grid: List[List[int]]
        :type hits: List[List[int]]
        :rtype: List[int]
        """

        m, n = len(grid), len(grid[0])
        
        # Connect unconnected bricks and 
        def dfs(i, j):
            if not (0<=i<m and 0<=j<n) or grid[i][j]!=1:
                return 0
            ret = 1
            grid[i][j] = 2
            ret += sum(dfs(x, y) for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)])
            return ret
        
        # Check whether (i, j) is connected to Not Falling Bricks
        def is_connected(i, j):
            return i==0 or any([0<=x<m and 0<=y<n and grid[x][y]==2 for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]])
        
        # Mark whether there is a brick at the each hit
        for i, j in hits:
            grid[i][j] -= 1
                
        # Get grid after all hits
        for i in range(n):
            dfs(0, i)
        
        # Reversely add the block of each hits and get count of newly add bricks
        ret = [0]*len(hits)
        for k in reversed(range(len(hits))):
            i, j = hits[k]
            grid[i][j] += 1
            if grid[i][j]==1 and is_connected(i, j):
                ret[k] = dfs(i, j)-1
            
        return ret  

Python:htm

class UnionFind(object):
    def __init__(self, n):
        self.set = range(n+1)
        self.size = [1]*(n+1)
        self.size[-1] = 0

    def find_set(self, x):
        if self.set[x] != x:
            self.set[x] = self.find_set(self.set[x])  # path compression.
        return self.set[x]

    def union_set(self, x, y):
        x_root, y_root = map(self.find_set, (x, y))
        if x_root == y_root:
            return False
        self.set[min(x_root, y_root)] = max(x_root, y_root)
        self.size[max(x_root, y_root)] += self.size[min(x_root, y_root)]
        return True

    def top(self):
        return self.size[self.find_set(len(self.size)-1)]


class Solution(object):
    def hitBricks(self, grid, hits):
        """
        :type grid: List[List[int]]
        :type hits: List[List[int]]
        :rtype: List[int]
        """
        def index(C, r, c):
            return r*C+c

        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        R, C = len(grid), len(grid[0])

        hit_grid = [row[:] for row in grid]
        for i, j in hits:
            hit_grid[i][j] = 0

        union_find = UnionFind(R*C)
        for r, row in enumerate(hit_grid):
            for c, val in enumerate(row):
                if not val:
                    continue
                if r == 0:
                    union_find.union_set(index(C, r, c), R*C)
                if r and hit_grid[r-1][c]:
                    union_find.union_set(index(C, r, c), index(C, r-1, c))
                if c and hit_grid[r][c-1]:
                    union_find.union_set(index(C, r, c), index(C, r, c-1))

        result = []
        for r, c in reversed(hits):
            prev_roof = union_find.top()
            if grid[r][c] == 0:
                result.append(0)
                continue
            for d in directions:
                nr, nc = (r+d[0], c+d[1])
                if 0 <= nr < R and 0 <= nc < C and hit_grid[nr][nc]:
                    union_find.union_set(index(C, r, c), index(C, nr, nc))
            if r == 0:
                union_find.union_set(index(C, r, c), R*C)
            hit_grid[r][c] = 1
            result.append(max(0, union_find.top()-prev_roof-1))
        return result[::-1]

C++:blog

// Time:  O(r * c)
// Space: O(r * c)

class Solution {
public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        static const vector<pair<int, int>> directions{{-1,  0}, { 1,  0},
                                                       { 0,  1}, { 0, -1}};
        const int R = grid.size();
        const int C = grid[0].size();
        const auto index = [&C](int r, int c) { return r * C + c; };

        vector<vector<int>> hit_grid(grid);
        for (const auto& hit : hits) {
            hit_grid[hit[0]][hit[1]] = 0;
        }

        UnionFind union_find(R * C);
        for (int r = 0; r < hit_grid.size(); ++r) {
            for (int c = 0; c < hit_grid[r].size(); ++c) {
                if (!hit_grid[r][c]) {
                    continue;
                }
                if (r == 0) {
                    union_find.union_set(index(r, c), R * C);
                }
                if (r && hit_grid[r - 1][c]) {
                    union_find.union_set(index(r, c), index(r - 1, c));
                }
                if (c && hit_grid[r][c - 1]) {
                    union_find.union_set(index(r, c), index(r, c - 1));
                }
            }
        }

        vector<int> result;
        for (int i = hits.size() - 1; i >= 0; --i) {
            const auto r = hits[i][0], c = hits[i][1];
            const auto prev_roof = union_find.top();
            if (grid[r][c] == 0) {
                result.emplace_back(0);
                continue;
            }
            for (const auto& d : directions) {
                const auto nr = r + d.first, nc = c + d.second;
                if (0 <= nr && nr < R &&
                    0 <= nc && nc < C &&
                    hit_grid[nr][nc]) {
                    union_find.union_set(index(r, c), index(nr, nc));
                }
            }
            if (r == 0) {
                union_find.union_set(index(r, c), R * C);
            }
            hit_grid[r][c] = 1;
            result.emplace_back(max(0, union_find.top() - prev_roof - 1));
        }
        reverse(result.begin(), result.end());
        return result;
    }

private:
    class UnionFind {
        public:
            UnionFind(const int n) : set_(n + 1), size_(n + 1, 1) {
                iota(set_.begin(), set_.end(), 0);
                size_.back() = 0;
            }

            int find_set(const int x) {
               if (set_[x] != x) {
                   set_[x] = find_set(set_[x]);  // Path compression.
               }
               return set_[x];
            }

            bool union_set(const int x, const int y) {
                int x_root = find_set(x), y_root = find_set(y);
                if (x_root == y_root) {
                    return false;
                }
                set_[min(x_root, y_root)] = max(x_root, y_root);
                size_[max(x_root, y_root)] += size_[min(x_root, y_root)];
                return true;
            }

            int top() {
                return size_[find_set(size_.size() - 1)];
            }

        private:
            vector<int> set_;
            vector<int> size_;
    };
};

  

  

All LeetCode Questions List 题目汇总