题解：CF1015E1 Stars Drawing (Easy Edition)

· · 题解

题解 CF1015E1

第一眼就考虑搜索。因为 n,m 都只有 100，所以对于每个点都暴力判断 O(nm(n+m)) 的复杂度是可以接受的。然后为当前十字的所有点打上标记并记下中心点。最后扫一遍 O(nm) 找有没有 "*" 点未被打上标记。

具体细节详见代码。

貌似可以预处理出 getlen() 的结果把时间复杂度优化到 O(nm)。

但是我懒。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5; 
int a[N],k[N],vis[N][N];
int n,m,cnt;
char g[N][N];
struct str{
    int x,y,w;

}pt[N*N];//中心点结构体记录答案,x,y为坐标,w为大小
int getlenth(int x,int y,int w)//暴力搜索当前可延展距离
{//w为方向标识符,1下2上3左4右
    if(x<1||x>n||y<1||y>m||g[x][y]=='.')return 0;
  //无法延展
    if(w==1)return getlenth(x-1,y,1)+1;
    if(w==2)return getlenth(x+1,y,2)+1;
    if(w==3)return getlenth(x,y-1,3)+1;
    if(w==4)return getlenth(x,y+1,4)+1;
}
void bj(int x,int y,int w,int d)//标记十字,w为仍需延展距离,d为方向标识符
{
    if(x<1||x>n||y<1||y>m||g[x][y]=='.'||w==0)return;
    vis[x][y]=1;//打上标记
    if(d==1)bj(x-1,y,w-1,1);
    if(d==2)bj(x+1,y,w-1,2);
    if(d==3)bj(x,y-1,w-1,3);
    if(d==4)bj(x,y+1,w-1,4);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(g[i][j]=='.')continue;//暴搜
            int s=getlenth(i,j,1),x=getlenth(i,j,2);
          //此处时间复杂度为O(n)
            int z=getlenth(i,j,3),y=getlenth(i,j,4);
          //此处时间复杂度为O(m)
            int p=min(min(s,z),min(x,y));
            if(p>1)//由于getlen的统计是从中心点开始的,所以p需-1
            {
                    pt[++cnt]={i,j,p-1};
                    for(int k=1;k<=4;k++) 
                        bj(i,j,p,k);
            }
          //由于题目spj,对于每个中心点我们可以只统计最大的十字
        }
    }
    bool xb=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(g[i][j]=='*'&&vis[i][j]==0)
            {
                cout<<-1;
                return 0;
            }//扫到不在任何十字中的点
            if(g[i][j]=='*')xb=1;//非全'.'图
        }
    }
    if(cnt==0&&xb==1)//一个十字也没有(似乎是多余的)
    {
        cout<<-1;
        return 0;
    }
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++)
    {
        cout<<pt[i].x<<" "<<pt[i].y<<" "<<pt[i].w<<endl;
    }
    //输出答案

    return 0;
}

Ciallo~☆