解题思路:(贪心+优先队列+覆盖关系映射)


我们可以使用贪心策略:每次选择覆盖区域内1的个数最少的T字形进行操作。这样做的目的是为了尽可能少地消耗1,从而进行更多的操作。但是,由于操作后会影响其他T字形,因此需要动态更新受影响的操作。


为了高效更新,我们需要知道每个位置被哪些T字形操作覆盖。这样,当一个位置被置0后,我们可以更新所有覆盖该位置的T字形操作的1的计数。




注意事项:1.边界处理2.效率问题3.时间复杂度


参考代码:

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <tuple>

using namespace std;


const vector<vector<pair<int, int>>> OFFSETS = {

    {{-1,0}, {0,0}, {1,0}, {0,1}},   // 向下开口

    {{-1,0}, {0,0}, {1,0}, {0,-1}},   // 向上开口

    {{0,-1}, {0,0}, {0,1}, {1,0}},   // 向右开口

    {{0,-1}, {0,0}, {0,1}, {-1,0}}   // 向左开口

};


int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    

    int D;

    cin >> D;

    while (D--) {

        int n;

        cin >> n;

        vector<string> grid(n);

        int total_ones = 0;

        for (int i = 0; i < n; i++) {

            cin >> grid[i];

            for (char c : grid[i]) 

                if (c == '1') total_ones++;

        }

        

        // 三维数组存储每种T字形操作的1的个数

        vector<vector<vector<int>>> cnt(n, vector<vector<int>>(n, vector<int>(4, 0)));

        // 映射每个格子被哪些T字形操作覆盖

        vector<vector<vector<tuple<int, int, int>>>> grid_map(n, vector<vector<tuple<int, int, int>>>(n));

        

        // 小根堆(1的数量,中心x,中心y,类型)

        priority_queue<tuple<int, int, int, int>, 

                      vector<tuple<int, int, int, int>>, 

                      greater<tuple<int, int, int, int>>> pq;

        

        auto valid = [&](int x, int y) {

            return x >= 0 && x < n && y >= 0 && y < n;

        };


        // 预填充cnt数组和grid_map

        for (int x = 0; x < n; x++) {

            for (int y = 0; y < n; y++) {

                for (int type = 0; type < 4; type++) {

                    bool skip = false;

                    int ones = 0;

                    vector<pair<int, int>> points;

                    

                    for (auto [dx, dy] : OFFSETS[type]) {

                        int nx = x + dx, ny = y + dy;

                        if (!valid(nx, ny)) {

                            skip = true;

                            break;

                        }

                        points.push_back({nx, ny});

                    }

                    

                    if (skip) continue;

                    

                    for (auto [px, py] : points) {

                        if (grid[px][py] == '1') ones++;

                        grid_map[px][py].push_back(make_tuple(x, y, type));

                    }

                    cnt[x][y][type] = ones;

                    if (ones > 0) pq.push(make_tuple(ones, x, y, type));

                }

            }

        }


        int ops = 0;

        while (!pq.empty() && total_ones > 0) {

            auto [c_old, x, y, type] = pq.top();

            pq.pop();

            

            // 检查是否过期

            if (cnt[x][y][type] != c_old) continue;

            if (c_old == 0) continue;

            

            ops++;

            vector<pair<int, int>> points;

            for (auto [dx, dy] : OFFSETS[type]) {

                points.push_back({x + dx, y + dy});

            }

            

            // 遍历覆盖的每个点

            for (auto [px, py] : points) {

                if (grid[px][py] == '0') continue;

                

                // 清除该点

                grid[px][py] = '0';

                total_ones--;

                

                // 更新所有覆盖该点的T字形操作

                for (auto [x2, y2, type2] : grid_map[px][py]) {

                    if (cnt[x2][y2][type2] > 0) {

                        cnt[x2][y2][type2]--;

                        pq.push(make_tuple(cnt[x2][y2][type2], x2, y2, type2));

                    }


        }

            }

        }

        

        cout << ops << '\n';

    }

    return 0;

}



点赞(1)
 

0.0分

0 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论