通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

leetcode游戏算法 803. 打砖块

177人浏览 / 0人评论 / | 作者:whisper  | 分类: 游戏算法  | 标签: leetcode  | 

作者:whisper

链接:https://www.proprogrammar.com/article/838

声明:请尊重原作者的劳动,如需转载请注明出处


803. 打砖块

有一个 m x n 的二元网格,其中 1 表示砖块,0 表示空白。砖块 稳定(不会掉落)的前提是:

一块砖直接连接到网格的顶部,或者
至少有一块相邻(4 个方向之一)砖块 稳定 不会掉落时
给你一个数组 hits ,这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时,对应位置的砖块(若存在)会消失,然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落,它会立即从网格中消失(即,它不会落在其他稳定的砖块上)。

返回一个数组 result ,其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。

注意,消除可能指向是没有砖块的空白位置,如果发生这种情况,则没有砖块掉落。

示例 1:

输入:grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
输出:[2]
解释:
网格开始为:
[[1,0,0,0],
 [1,1,1,0]]
消除 (1,0) 处加粗的砖块,得到网格:
[[1,0,0,0]
 [0,1,1,0]]
两个加粗的砖不再稳定,因为它们不再与顶部相连,也不再与另一个稳定的砖相邻,因此它们将掉落。得到网格:
[[1,0,0,0],
 [0,0,0,0]]
因此,结果为 [2] 。

示例 2:

输入:grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
输出:[0,0]
解释:
网格开始为:
[[1,0,0,0],
 [1,1,0,0]]
消除 (1,1) 处加粗的砖块,得到网格:
[[1,0,0,0],
 [1,0,0,0]]
剩下的砖都很稳定,所以不会掉落。网格保持不变:
[[1,0,0,0], 
 [1,0,0,0]]
接下来消除 (1,0) 处加粗的砖块,得到网格:
[[1,0,0,0],
 [0,0,0,0]]
剩下的砖块仍然是稳定的,所以不会有砖块掉落。
因此,结果为 [0,0] 。

提示:

m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] 为 0 或 1
1 <= hits.length <= 4 * 104
hits[i].length == 2
0 <= xi <= m - 1
0 <= yi <= n - 1
所有 (xi, yi) 互不相同


这题是难题,我超时了,用的c++,先看一下吧

class Solution {
private:
int count = 0;
int dr[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
public:
    // 四方深搜到顶部,代码不长,效率不高,超时
    // 可能的优化: sz置0方法去掉,每处深搜使用之前深搜的结果
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        vector<int> res(hits.size(), 0);
        for(int i = 0; i < hits.size(); i++){
            vector<int> h = hits[i];
            if(grid[h[0]][h[1]]){
                grid[h[0]][h[1]] = 0;
                for(int* d: dr){
                    if(!keep(grid, h[0]+d[0], h[1]+d[1], (h[0]<<16)|(h[1]<<8)|1) && count){
                        res[i]+=count;
                        sz(grid, h[0]+d[0], h[1]+d[1]);
                    }
                    count = 0;
                }
            }
        }

        return res;
    }

    bool keep(vector<vector<int>>& grid, int x, int y, int cur){
        if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || !grid[x][y] || grid[x][y] == cur) return false;
        if(x == 0 && grid[x][y]) return true;
        if(((grid[x][y]&0xffff00)>>8)==((cur&0xffff00)>>8))return true;

        grid[x][y] = cur;
        count++;
        return keep(grid, x-1, y, cur) || keep(grid, x, y-1, cur) || keep(grid, x, y+1, cur) || keep(grid, x+1, y, cur);
    }

    int sz(vector<vector<int>>& grid, int x, int y){
        if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || !grid[x][y]) return 0;
        grid[x][y] = 0;
        return sz(grid, x-1, y) | sz(grid, x, y-1) | sz(grid, x, y+1) | sz(grid, x+1, y);
    }
}

直观解法,打一块看相邻会不会掉落


再看一下官方解法

class Solution {
    // 官方解法
    class UnionFind {
    private:
        vector<int> f, sz;
    public:
        UnionFind(int n): f(n), sz(n) {
            for (int i = 0; i < n; i++) {
                f[i] = i;
                sz[i] = 1;
            }
        }

        int find(int x) {
            if (f[x] == x) {
                return x;
            }
            int newf = find(f[x]);
            f[x] = newf;
            return f[x];
        }

        void merge(int x, int y) {
            int fx = find(x), fy = find(y);
            if (fx == fy) {
                return;
            }
            f[fx] = fy;
            sz[fy] += sz[fx];
        }

        int size(int x) {
            return sz[find(x)];
        }
    };

    // https://leetcode-cn.com/problems/bricks-falling-when-hit/solution/da-zhuan-kuai-by-leetcode-solution-szrq/
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        int h = grid.size(), w = grid[0].size();
        
        UnionFind uf(h * w + 1);
        vector<vector<int>> status = grid;
        for (int i = 0; i < hits.size(); i++) {
            status[hits[i][0]][hits[i][1]] = 0;
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (status[i][j] == 1) {
                    if (i == 0) {
                        uf.merge(h * w, i * w + j);
                    }
                    if (i > 0 && status[i - 1][j] == 1) {
                        uf.merge(i * w + j, (i - 1) * w + j);
                    }
                    if (j > 0 && status[i][j - 1] == 1) {
                        uf.merge(i * w + j, i * w + j - 1);
                    }
                }
            }
        }
        const vector<pair<int, int>> directions{{0, 1},{1, 0},{0, -1},{-1, 0}};
        vector<int> ret(hits.size(), 0);
        for (int i = hits.size() - 1; i >= 0; i--) {
            int r = hits[i][0], c = hits[i][1];
            if (grid[r][c] == 0) {
                continue;
            }
            int prev = uf.size(h * w);

            if (r == 0) {
                uf.merge(c, h * w);
            }
            for (const auto [dr, dc]: directions) {
                int nr = r + dr, nc = c + dc;
                
                if (nr >= 0 && nr < h && nc >= 0 && nc < w) {
                    if (status[nr][nc] == 1) {
                        uf.merge(r * w + c, nr * w + nc);
                    }
                }
            }
            int size = uf.size(h * w);
            ret[i] = max(0, size - prev - 1);
            status[r][c] = 1;
        }
        return ret;
    }
};

官方是从后向前,先考虑最后一次,再向前考虑,看成图,使用并查集(用到并查集基本都是难题),把从前向后的减点图不连通变成从后向前的加点图连通的问题

官方题解


亲爱的读者:有时间可以点赞评论一下

点赞(1) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告