原题链接：点这里或这里
解法
其实这题应该要缩短时间限制，不然感觉暴力都可以卡过去。
这里提供一个 $O(nm \cdot\log \min(n,m))$ 的做法。
首先 E1 的暴力做法比较好实现：
- 枚举每一个 $‘*‘$ 的位置，并且尽可能向四个方向扩展，标记每一个扩展的位置。
- 如果出现没有标记过的 $‘*‘$，输出 $-1$，否则输出刚刚扩展的方案。
这个想法的时间复杂度是三次方级别的，我们应将其优化。
如何快速定位每个位置的最大扩展长度
我们可以先只考虑一行或一列的情况。
如果我们把 $‘*‘$ 的值视作 $1$，其余视作 $0$，那么一段区间的价值和就是区间中 $‘*‘$ 的数量。
所以，如果区间 $[l,r]$ 内全是 $‘*‘$ 而没有 $‘.‘$，那么该区间的价值和为 $r-l+1$。
而我们扩展的时候，需要保证的是这个「星星图案」内没有 $‘.‘$ 。
若从 $(i,j)$ 扩展长度 $k$，那么需要保证第 $i$ 行的第 $j-k~ \sim j+k$ 列位置全部为 $‘*‘$，第 $j$ 列同理。
上述条件，等价于第 $i$ 行的 $‘*‘$ 总数为 $j+k-(j-k)+1=2k+1$。
如果不理解，可以看如下例子：
...*... ...*... ...*... ******* ...*... ...*... ...*...
这是一个大小为 $3$ 的「星星图案」。
其中有「星星图案」的行、列的区间 $‘*‘$ 数均为 $2\times3+1=7$。
而如下这个图没有长度为 $3$「星星图案」。
...*... ....... ...*... ******* ...*... ...*... ...*...
原因是若以 $(4,4)$ 为中心扩展 $3$ 格，那么第 $4$ 列的区间和为 $6$，与 $7$ 不相等。
静态维护区间和，我们就可以使用前缀和。
只不过这是一个二维图案，我们需要分别对它进行行、列的前缀和。
如何优化时间复杂度
可以发现，如果以某点为中心，可以向外扩展 $k+1$ 个单位，那么它也绝对可以向外扩展 $k$ 个单位。
因此，扩展的长度相对条件具有单调性，我们可以二分查找。
如何快速判断无解
如果我们一个一个标记每个 $‘*‘$ 的位置是否访问过，那复杂度就退化了。
但是我们有足够的复杂度可以在最后时刻一次性访问每个位置，判断它是否被访问过。
所以，将整个区间进行标记，可以是用差分，最后用前缀和求得答案。
注意一个「星星图案」的行、列都要标记。
有人会有所担心行、列若分别标记一次，中心会被标记两次，影响答案。
其实并不会，因为最后只有行、列的差分数组前缀和均为 $0$，才代表这个位置没有访问过。因此访问次数我们并不需要在意。
以下是代码，不理解的地方可以参考注释
#include <bits/stdc++.h> #define INF 1e9 #define eps 1e-6 typedef long long ll; using namespace std; int n, m, suml[1010][1010], sumu[1010][1010], l, r; int addl[1010][1010], addw[1010][1010], sl[1010][1010], sw[1010][1010]; int ss, ans1[1000010], ans2[1000010], ans3[1000010]; bool vis[1010][1010]; char s[1010][1010]; bool check(int i, int j, int x){ // 判断是否全为 * if(sumu[i + x][j] - sumu[i - x - 1][j] != x + x + 1) return 0; if(suml[i][j + x] - suml[i][j - x - 1] != x + x + 1) return 0; return 1; } int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) // 行和列分别前缀和 suml[i][j] = suml[i][j - 1] + (s[i][j] == ‘*‘); for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) sumu[j][i] = sumu[j - 1][i] + (s[j][i] == ‘*‘); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){ // 扩展范围不能超出边界 l = 0, r = min(i - 1, min(n - i, min(j - 1, m - j))); while(l < r){ int mid = (l + r + 1) >> 1; if(check(i, j, mid)) l = mid; else r = mid - 1; } if(l != 0){ // 记录答案、标记差分数组 ans1[++ss] = i, ans2[ss] = j, ans3[ss] = l; addl[i - l][j]++, addl[i + l + 1][j]--; addw[i][j - l]++, addw[i][j + l + 1]--; } } for(int i = 1; i <= n; i++) // 将差分数组进行前缀和得到访问记录 for(int j = 1; j <= m; j++) sw[i][j] = sw[i][j - 1] + addw[i][j]; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sl[i][j] = sl[i - 1][j] + addl[i][j]; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){ if(sw[i][j] == 0 && sl[i][j] == 0 && s[i][j] == ‘*‘){ // 没有访问过的 * 需要输出 -1 puts("-1"); return 0; } } cout << ss << endl; // 输出答案 for(int i = 1; i <= ss; i++) printf("%d %d %d\n", ans1[i], ans2[i], ans3[i]); return 0; }