c++ 背景 玩过商场中的人体打印墙吗？ 描述 给定一个 n × n 的矩阵，在其上进行若干次操作。每次操作，你可以将一个 k × k 的连续子矩阵里的所有数全部加上1或者全都减去1。 初始时，矩阵中有 m 个位置上的数不为 0 ，其他位置上的数均为 0。请问至少需要多少次操作，可以将矩阵中的所有数字都变为 0。 格式 输入 第一行三个整数 n, m, k 分别表示矩阵大小、非零格数和每次修改的连续子矩阵大小。 接下来 m 行，每行三个整数 x, y, z 表示初始时矩阵的第 x 行第 y列上的数为z 。 输出 一行，一个整数，表示最少操作次数。特别地，如果无法使矩阵中所有数都变为0，输出-1.

以下是一个使用 C++ 解决此问题的示例代码： ```cpp #include <iostream> #include <vector> #include <unordered_set> const int MAXN = 55; int n, m, k; int a[MAXN][MAXN]; bool vis[MAXN][MAXN]; // 检查是否可以通过操作将矩阵全部变为 0 bool check() { int sum = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { sum += a[i][j]; } } return sum == 0; } // 执行加 1 操作 void add(int x, int y) { for (int i = x; i < std::min(x + k, n); ++i) { for (int j = y; j < std::min(y + k, n); ++j) { a[i][j]++; } } } // 执行减 1 操作 void sub(int x, int y) { for (int i = x; i < std::min(x + k, n); ++i) { for (int j = y; j < std::min(y + k, n); ++j) { a[i][j]--; } } } int solve() { std::unordered_set<int> states; std::vector<std::pair<int, int>> ops; int step = 0; while (true) { states.clear(); for (int i = 0; i <= n - k; ++i) { for (int j = 0; j <= n - k; ++j) { // 先尝试加 1 操作 std::memcpy(a, a, sizeof(a)); add(i, j); if (check() && states.find(hash()) == states.end()) { states.insert(hash()); ops.push_back({i, j}); step++; if (check()) { return step; } } // 再尝试减 1 操作 std::memcpy(a, a, sizeof(a)); sub(i, j); if (check() && states.find(hash()) == states.end()) { states.insert(hash()); ops.push_back({i, j}); step++; if (check()) { return step; } } } } if (ops.empty()) { return -1; } auto op = ops.back(); ops.pop_back(); if (a[op.first][op.second] == 1) { sub(op.first, op.second); } else { add(op.first, op.second); } } return -1; } int main() { std::cin >> n >> m >> k; for (int i = 0; i < m; ++i) { int x, y, z; std::cin >> x >> y >> z; a[x - 1][y - 1] = z; } int ans = solve(); std::cout << ans << std::endl; return 0; } ``` 这段代码实现了一个暴力搜索的解法，通过不断尝试各种操作组合来找到将矩阵全部变为 0 的最少操作次数。 [2024-10-24 14:06:12 | AI写代码神器 | 814点数解答]