喵~ 各位算法大师们好呀！这里是热爱解题的喵娘 Mya！✨
今天我们要挑战的是一个非常有趣的画图问题，Codeforces 上的 1015E2 - Stars Drawing (Hard Edition)。光听名字就觉得很浪漫，对不对？用星星来画满整个夜空，想想就觉得好激动呀！那么，就让 Mya 陪着大家一起，把这片由 * 组成的夜空点亮吧！
题目大意
简单来说，题目给了我们一个 N x M 大小的网格，里面有些地方是星星 *，有些地方是空的 .。我们的任务呢，就是用一种特殊的“十字星”图形，把所有 * 的地方都给覆盖掉。
这种“十字星”长什么样呢？它有一个中心点 *，然后向上下左右四个方向伸出长度相等的光芒。光芒的长度（我们称之为“大小”）必须是正数，也就是至少为1。
就像这样：
. . .
* * *
*** *** ***
* ***** *****
* * * *******
*** *****
* ***
. *
.
大小为1 大小为2 大小为3我们需要找到一种用这些十字星画出给定网格的方法。如果可以，就输出需要多少颗星星，以及每颗星星的中心坐标和大小。如果无论如何都画不出来，就要告诉出题人：“这办不到喵！” (-1)。
解题方法
喵喵的思路其实很直接，也很“贪心”哦！
贪心寻找： 既然要覆盖所有的
*，那对于每一个*，如果它能成为一个十字星的中心，我们肯定希望以它为中心的这颗星星越大越好，这样一次就能覆盖更多的*，对吧？所以，我们的第一步就是遍历整个网格，对于每一个*，都计算出以它为中心能画出的最大的十字星是多大，并把这些可能的星星都记录下来。验证覆盖： 找到了所有可能的最大星星之后，问题就来了：把这些星星全部画上去，是不是就能恰好覆盖所有原始的
*呢？会不会有某个角落的*，它虽然是*，但它无法成为任何一个十字星的一部分，也被我们漏掉了呢？所以，我们需要一个高效的方法来验证，我们找到的这些星星集合，是否能完整地覆盖所有*。
如果所有 * 都被覆盖了，那就成功啦！否则，就是无解。
这个思路听起来很简单，但“验证覆盖”这一步如果处理不好，可是会很慢的哦！下面我们来看看具体怎么实现吧！
题解详解
第一步：预处理 - 计算每个方向的连续 * 长度
为了快速知道在 (r, c) 这个点能画出多大的星星，我们需要知道从它出发，上下左右四个方向最远能延伸多远。这可以用动态规划（DP）来飞快地算出来，喵~
我们创建四个和网格一样大的二维数组：up, down, left, right。
up[r][c]：从(r, c)向上（包括自身）有多少个连续的*。down[r][c]：从(r, c)向下（包括自身）有多少个连续的*。left[r][c]：从(r, c)向左（包括自身）有多少个连续的*。right[r][c]：从(r, c)向右（包括自身）有多少个连续的*。
计算方法如下：
up和left的计算，从左上到右下遍历：cppif (grid[r][c] == '*') { up[r][c] = up[r-1][c] + 1; left[r][c] = left[r][c-1] + 1; }down和right的计算，从右下到左上遍历：cppif (grid[r][c] == '*') { down[r][c] = down[r+1][c] + 1; right[r][c] = right[r][c+1] + 1; }
做完这步预处理，对于任何一个点，它能伸出的“光芒”有多长就一清二楚啦！
第二步：寻找所有可能的最大星星
现在，我们再次遍历整个网格。对于每个是 * 的格子 (r, c)，以它为中心能画出的最大十字星的大小 s 是多少呢？当然是它四个方向延伸长度里的最小值啦！
s = min(up[r][c], down[r][c], left[r][c], right[r][c]) - 1
这里要 -1 是因为，比如向上有3个连续的 *，那么光芒长度其实是2（中心点占了1个）。
如果计算出的 s > 0，说明这里至少可以画一个大小为1的星星。我们就把这颗星星的信息 (r, c, s) 存起来。
第三步：验证覆盖（最关键的一步！）
我们已经有了一个星星列表。现在要验证它们是否覆盖了所有 *。一个个格子去模拟画图太慢了，会超时的说！
这里就要请出我们的秘密武器——差分数组！💖
我们可以把一个十字星的覆盖拆成一个横向覆盖和一个纵向覆盖。
- 横向光芒覆盖了第
r行的[c-s, c+s]列。 - 纵向光芒覆盖了第
c列的[r-s, r+s]行。
我们可以用两个差分数组 covered_row 和 covered_col 来记录覆盖情况。
- 对于每颗星星
(r, c, s)：- 我们在
covered_row[r][c-s]处+1，在covered_row[r][c+s+1]处-1。 - 我们在
covered_col[r-s][c]处+1，在covered_col[r+s+1][c]处-1。
- 我们在
等所有星星都标记完后，我们对 covered_row 的每一行和 covered_col 的每一列分别求前缀和。
covered_row[r][c]的值就表示(r, c)这个点被横向光芒覆盖了多少次。covered_col[r][c]的值就表示(r, c)这个点被纵向光芒覆盖了多少次。
最后，我们再遍历一次网格。如果发现某个格子 (r, c) 本来是 *，但是 covered_row[r][c] 和 covered_col[r][c] 同时为0，那就意味着这个 * 没有被任何光芒覆盖到。它是一只“漏网之鱼”！这说明我们的方案不行，只能遗憾地输出 -1 了喵。
第四步：输出结果
如果检查完所有 * 都被完美覆盖了，那就太棒啦！我们把记录下来的星星数量和它们的坐标、大小打印出来就好啦。任务完成，喵~
下面是完整的解题代码，Mya 已经加上了详细的注释哦！
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::string> grid(n);
for (int i = 0; i < n; ++i) {
std::cin >> grid[i];
}
// DP 表格，用于存储四个方向连续 '*' 的长度
// 为了方便处理边界，我们使用 1-based 索引
std::vector<std::vector<int>> up(n + 2, std::vector<int>(m + 2, 0));
std::vector<std::vector<int>> down(n + 2, std::vector<int>(m + 2, 0));
std::vector<std::vector<int>> left(n + 2, std::vector<int>(m + 2, 0));
std::vector<std::vector<int>> right(n + 2, std::vector<int>(m + 2, 0));
// 从左上到右下计算 up 和 left
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (grid[i - 1][j - 1] == '*') {
up[i][j] = up[i - 1][j] + 1;
left[i][j] = left[i][j - 1] + 1;
}
}
}
// 从右下到左上计算 down 和 right
for (int i = n; i >= 1; --i) {
for (int j = m; j >= 1; --j) {
if (grid[i - 1][j - 1] == '*') {
down[i][j] = down[i + 1][j] + 1;
right[i][j] = right[i][j + 1] + 1;
}
}
}
std::vector<std::tuple<int, int, int>> stars;
// 寻找所有可能的最大星星
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (grid[i - 1][j - 1] == '*') {
// 星星的大小是四个方向延伸长度的最小值 - 1
int size = std::min({up[i][j], down[i][j], left[i][j], right[i][j]}) - 1;
if (size > 0) {
stars.emplace_back(i, j, size);
}
}
}
}
// 使用二维差分数组来检查覆盖情况
std::vector<std::vector<int>> covered_row(n + 2, std::vector<int>(m + 2, 0));
std::vector<std::vector<int>> covered_col(n + 2, std::vector<int>(m + 2, 0));
for (const auto& star : stars) {
int r, c, s;
std::tie(r, c, s) = star;
// 标记横向光芒的覆盖范围
covered_row[r][c - s]++;
if (c + s + 1 <= m + 1) {
covered_row[r][c + s + 1]--;
}
// 标记纵向光芒的覆盖范围
covered_col[r - s][c]++;
if (r + s + 1 <= n + 1) {
covered_col[r + s + 1][c]--;
}
}
// 计算前缀和，得到每个格子的实际覆盖次数
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
covered_row[i][j] += covered_row[i][j - 1];
}
}
for (int j = 1; j <= m; ++j) {
for (int i = 1; i <= n; ++i) {
covered_col[i][j] += covered_col[i - 1][j];
}
}
// 最终检查：确保所有 '*' 都被覆盖了
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
// 如果一个格子是 '*' 但横向和纵向覆盖次数都为0，则无解
if (grid[i - 1][j - 1] == '*' && covered_row[i][j] == 0 && covered_col[i][j] == 0) {
std::cout << -1 << "\n";
return;
}
}
}
// 如果检查通过，输出结果
std::cout << stars.size() << "\n";
for (const auto& star : stars) {
std::cout << std::get<0>(star) << " " << std::get<1>(star) << " " << std::get<2>(star) << "\n";
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
solve();
return 0;
}知识点介绍
这道题用到了两个非常经典的算法思想，学到就是赚到喵！
动态规划 (Dynamic Programming) DP 是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。它的核心思想是“记忆化”，避免重复计算。在这道题里，我们计算
up[i][j]时，直接利用了已经算好的up[i-1][j]的结果，这就是DP的应用。它让我们的预处理步骤变得非常高效！差分数组 (Difference Array) 差分数组是处理“区间修改”问题的神器！当我们需要对一个数组的某个区间
[L, R]内所有元素都加上一个值时，如果一个个去加，时间复杂度是 O(N)。但用差分数组，我们只需要在diff[L]加上这个值，在diff[R+1]减去这个值，两次操作都是 O(1)！最后通过一次前缀和，就能还原出原数组。 这道题里，画一个星星的光芒，就相当于对某一行或某一列的一个区间进行了“覆盖”操作。我们巧妙地用两个一维差分数组（一个管行，一个管列）来解决了这个二维的覆盖问题，避免了 O(N*M) 的模拟，大大降低了验证步骤的复杂度！
好啦，这次的星星就画到这里啦！希望大家都能明白喵~ 如果你喜欢 Mya 的题解，别忘了给个赞哦！下次再见！💖