题目描述
小蓝正在玩一款游戏，游戏中有一个n × n大小的 01 矩阵 Ai, j 。小蓝每次需要选择一个T字型的区域，且这个区域内至少要有一个 1 。选中后，这个区域内所有的元素都会变成 0。给定游戏目前的矩阵，小蓝想知道他最多可以进行多少次上述操作。 T字型区域是指形如 (x − 1, y) (x, y) (x + 1, y) (x, y + 1) 的四个点所形成的区 域。其旋转 90, 180, 270 度的形式同样也视作 T 字形区域。
输入格式
输入包含多组数据。输入的第一行包含一个整数 D 表示数据组数。对于每组数据，第一行包含一个整数n。接下来n行每行包含n个0或1，表示矩阵Ai, j的每个位置的值。
输出格式
输出 D 行，每行包含一个整数表示小蓝最多可以对当前询问中的矩阵操作的次数。
样例输入
1 3 001 011 111
样例输出
5
提示
我们用 X 表示某次操作选中的 T 字形，以下给出一种可行方案：
001 XXX 0X0 00X 0X0 X00
011 => 0X1 => XXX => 0XX => XX0 => XX0
111 111 111 11X 1X0 X00
对于 10% 的评测用例，n = 3 ；
对于 40% 的评测用例，n ≤ 30 ；
对于所有评测用例，3 ≤ n ≤ 2000，矩阵中仅含 0 和 1 。
解题思路:（贪心+优先队列+覆盖关系映射）我们可以使用贪心策略：每次选择覆盖区域内1的个数最少的T字形进行操作。这样做的目的是为了尽可能少地消耗1，从而进行更多的操作。但是，由于操作后会影响其他T字形，因此需要动态更新受影响的操作。为了高效更新，我们需要知道每个位置被哪些T字形操作覆盖。这样，当一个位置被置0后，我们可以更新所有覆盖该位置的T字形操作的1的计数。
注意事项:1.边界处理2.效率问题3.时间复杂度
题解答案：全网独一份答案 C语言网上的三份解答均为版主提供
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>
using namespace std;
<br>
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}} // 向左开口
<br>
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;
};
<br>
// 预填充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));
}
}
}
<br>
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
