题目：Stars Drawing
思路：
由于不需要求最小覆盖，就可以在所有可覆盖的地方都覆盖上一个十字形。
对于每个点，预处理出它上下左右能延伸的最长距离，那么可以有它覆盖上的十字形的size为min{up,down,right,left}。
然后在处理出两个前缀和数组judgerow、judgecol，在每个可处理出的十字形的上下左右端点相应的进行加1减1。
当一个点为*且judgerow和judgecol均为0时，这个点不可被覆盖。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 1000 int n,m;
char a[maxn+5][maxn+5];
int Up[maxn+5][maxn+5],Down[maxn+5][maxn+5],Left[maxn+5][maxn+5],Right[maxn+5][maxn+5];int ans=0;
int X[maxn*maxn+5],Y[maxn*maxn+5],s[maxn*maxn+5];int judgerow[maxn+5][maxn+5],judgecol[maxn+5][maxn+5];void readin() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) {scanf("%s",a[i]+1);}
}void init() {for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {if(a[i][j]=='.') continue;Up[i][j]=Up[i-1][j]+1;Right[i][j]=Right[i][j-1]+1;}}for(int i=n;i>=1;i--) {for(int j=m;j>=1;j--) {if(a[i][j]=='.') continue;Down[i][j]=Down[i+1][j]+1;Left[i][j]=Left[i][j+1]+1;}}
}bool judge() {for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {if(a[i][j]=='.') continue;int Min=min(min(Up[i][j],Down[i][j]),min(Left[i][j],Right[i][j]))-1;if(Min<=0) continue;judgecol[i][j-Min]++,judgecol[i][j+Min+1]--;judgerow[i-Min][j]++,judgerow[i+Min+1][j]--;}}for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {judgecol[i][j]+=judgecol[i][j-1];judgerow[i][j]+=judgerow[i-1][j];if(a[i][j]=='*'&&!judgecol[i][j]&&!judgerow[i][j]) return false;}}return true;
}int count() {for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {if(a[i][j]=='.') continue;int Min=min(min(Up[i][j],Down[i][j]),min(Left[i][j],Right[i][j]))-1;if(Min<=0) continue;ans++;X[ans]=i,Y[ans]=j,s[ans]=Min;}}
}void print() {printf("%d\n",ans);for(int i=1;i<=ans;i++) {printf("%d %d %d\n",X[i],Y[i],s[i]);}
}int main() {readin();init();if(!judge()) {printf("-1");return 0;}count();print();return 0;
}