蓝桥杯2023年第十四届省赛真题-T字消除

解题思路:（贪心+优先队列+覆盖关系映射）我们可以使用贪心策略：每次选择覆盖区域内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;

}

// THEBUG MUXI

//byTHEBUG木析