【CF1015E】Stars Drawing

题意

? 给你一副由 ‘.‘ 和 ‘*‘ 组成的图,问你能否用任意多个由’*‘组成的十字组成该图,十字大小任意,且可以互相交叉、覆盖。

? 十字不能是一个点,也就是十字最小是:

? 【CF1015E】Stars Drawing


思路

? 没看出easy和hard本质的区别(可能hard有点卡常?),暴力,遍历整张图,遇到可以放十字的地方就放个尽可能大的十字,记录十字的位置和大小,并标记被十字覆盖的地方。遍历后与所给的图对比,看是否有‘*‘但该处未被标记,若有则输出-1。


code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll maxn=1000+10;
int cnt[maxn][maxn],n,m;
string g[maxn];
struct node
{
    int i,j,len;
    node(int ii,int jj,int len1) {i=ii,j=jj,len=len1;}
};
vector <node> ans;

int check(int i,int j)
{
    if(g[i][j]!=‘*‘) return 0;
    if(i==0||j==0||i==n-1||j==m-1) return 0;
    if(g[i+1][j]!=‘*‘||g[i-1][j]!=‘*‘||g[i][j+1]!=‘*‘||g[i][j-1]!=‘*‘) return 0;
    return 1;
}
void solve(int i,int j)
{
    int maxx=1,k=1,res=0x3f3f3f3f;
    while(i+k<n&&g[i+k][j]==‘*‘) maxx=max(maxx,k),k++;
    res=min(res,maxx),k=1,maxx=1;
    while(i-k>=0&&g[i-k][j]==‘*‘) maxx=max(maxx,k),k++;
    res=min(res,maxx),k=1,maxx=1;
    while(j+k<m&&g[i][j+k]==‘*‘) maxx=max(maxx,k),k++;
    res=min(res,maxx),k=1,maxx=1;
    while(j-k>=0&&g[i][j-k]==‘*‘) maxx=max(maxx,k),k++;
    res=min(res,maxx),k=1,maxx=1;
    for(int l=0;l<=res;l++)
    {
        cnt[i+l][j]=1;
        cnt[i-l][j]=1;
        cnt[i][j+l]=1;
        cnt[i][j-l]=1;
    }
    ans.push_back(node(i,j,res));
}

int main()
{
    ios::sync_with_stdio(0);
    while(cin>>n>>m)
    {
        for(int i=0;i<n;i++) cin>>g[i];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(check(i,j)) solve(i,j);
            }
        }
        int flag=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(g[i][j]==‘*‘&&cnt[i][j]==0)
                {
                    flag=1;
                    break;
                }
            }
            if(flag) break;
        }
        if(flag) cout<<"-1\n"; 
        else
        {
            cout<<ans.size()<<"\n";
            for(node a:ans) cout<<a.i+1<<" "<<a.j+1<<" "<<a.len<<"\n";
        }
    }
    return 0;
}

【CF1015E】Stars Drawing

上一篇:Win7远程计算机或设备将不接受连接怎么办


下一篇:API-文件操作