E - Polycarp and Snakes

题意：在一个全是点的图上开始画线，每次将一行或一列任意长度染成字母，一笔染一种字母，字母必须从a开始连续到后面某个字母可以覆盖。

问所给图案是否满足，若满足输出它画了几个字母，然后输出这每个字母开始和截止画的横纵坐标。

思路：存图，模拟，用个x1,x2,y1,y2记录每个字母出现位置的最小最大的横纵坐标，对于每个字母如果它的x1,x2,y1,y2不是初始值的话，那么它在图上就出现过（没有被覆盖掉），那么这个字母必然满足，x1==x2||y1==y2；

#include<bits/stdc++.h>

using namespace std;

char mp[][];

int x1[],x2[],y1[],y2[];

int main()

{

    int n,m;

    int it=;

    scanf("%d",&it);

    while(it--)

    {

        scanf("%d%d",&n,&m);

        for(int i=; i<=n; i++)

            scanf("%s",mp[i]+);

        for(int i=; i<=; i++)

        {

            x1[i]=;

            y1[i]=;

            x2[i]=-;

            y2[i]=-;

        }

        for(int i=; i<=n; i++)

            for(int j=; j<=m; j++)

            {

                if(mp[i][j]!='.')

                {

                    int num=mp[i][j]-'a'+;

                    x1[num]=min(x1[num],i);

                    x2[num]=max(x2[num],i);

                    y1[num]=min(y1[num],j);

                    y2[num]=max(y2[num],j);

                }

            }

        int flag=;

        int live[];

        int cnt=;

        memset(live,,sizeof(live));

        for(int i=; i<=; i++)

        {

            if(x1[i]!=&&y1[i]!=)

            {

                if(x1[i]==x2[i])

                {

                    cnt=i;

                    for(int j=y1[i]; j<=y2[i]; j++)

                        if(mp[x1[i]][j]<('a'+i-))

                        {

                            flag=;

                            break;

                        }

                    live[i]=;

                }

                else if(y1[i]==y2[i])

                {

                    cnt=i;

                    for(int j=x1[i]; j<=x2[i]; j++)

                    {

                        if(mp[j][y1[i]]<('a'+i-))

                        {

                            flag=;

                            break;

                        }

                    }

                    live[i]=;

                }

                else

                {

                    flag=;

                    break;

                }

            }

        }

//    for(int i=1; i<=5; i++)

//        printf("%d %d %d %d\n",x1[i],x2[i],y1[i],y2[i]);

        if(flag==)

            printf("NO\n");

        else

        {

            printf("YES\n%d\n",cnt);

            for(int i=; i<=cnt; i++)

            {

                if(live[i]==)

                {

//                    printf("???");

                    for(int j=i+; j<=; j++)

                    {

                        if(live[j]==)

                        {

                            printf("%d %d %d %d\n",x1[j],y1[j],x2[j],y2[j]);

                            break;

                        }

                    }

                }

                else

                    printf("%d %d %d %d\n",x1[i],y1[i],x2[i],y2[i]);

            }

        }

    }

}

巴特西

E - Polycarp and Snakes

最新文章

热门文章