思路:

这题思路还是比较好的,对于这种十字形状的图形,我们可以设置一个表示这个点上下左右四个方向可以延续的长度是多少.
然后转移十分简单,这里就不写了.
然后我们贪心的把每个可以取的位子全部取了,都取.最后再前缀记录一下是否被全部覆盖,假如存在没有被覆盖的,那么答案就输出.否则就是所有存在里的答案了.

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5,M=4;//上,下,左,右 
struct Ans{
    int x,y,sz;
};
vector<Ans>ans;
char s[N][N];
int f[N][N][M],pre_x[N][N],pre_y[N][N];
int main()
{
    int n,m,dis;cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>s[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(s[i][j]=='*')
                f[i][j][0]=f[i-1][j][0]+1,f[i][j][2]=f[i][j-1][2]+1;
    for(int i=n;i>=1;i--)
        for(int j=m;j>=1;j--)
            if(s[i][j]=='*')
                f[i][j][1]=f[i+1][j][1]+1,f[i][j][3]=f[i][j+1][3]+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(s[i][j]=='*')
            {
                dis=min(min(f[i][j][0],f[i][j][1]),min(f[i][j][2],f[i][j][3]))-1;
                if(dis<1)    continue;
                ans.push_back({i,j,dis});
                pre_x[i-dis][j]++,pre_x[i+dis+1][j]--;
                pre_y[i][j-dis]++,pre_y[i][j+dis+1]--;
            }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            pre_x[i][j]+=pre_x[i-1][j],pre_y[i][j]+=pre_y[i][j-1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(s[i][j]=='*'&&pre_x[i][j]==0&&pre_y[i][j]==0)
            {
                puts("-1");return 0;
            }
    cout<<(int)ans.size()<<'\n';
    for(auto x:ans)
        cout<<x.x<<' '<<x.y<<' '<<x.sz<<'\n';
    return 0;
}