E

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[2005][2005];
int x1[30],x2[30],y1[30],y2[30];

int main()
{
    int n,m;
    int it=1;
    scanf("%d",&it);
    while(it--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
            scanf("%s",mp[i]+1);
        for(int i=1; i<=26; i++)
        {
            x1[i]=9999;
            y1[i]=9999;
            x2[i]=-9999;
            y2[i]=-9999;
        }
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
            {
                if(mp[i][j]!='.')
                {
                    int num=mp[i][j]-'a'+1;
                    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=1;
        int live[30];
        int cnt=0;
        memset(live,0,sizeof(live));
        for(int i=1; i<=26; i++)
        {
            if(x1[i]!=9999&&y1[i]!=9999)
            {
                if(x1[i]==x2[i])
                {
                    cnt=i;
                    for(int j=y1[i]; j<=y2[i]; j++)
                        if(mp[x1[i]][j]<('a'+i-1))
                        {
                            flag=0;
                            break;
                        }
                    live[i]=1;
                }
                else if(y1[i]==y2[i])
                {
                    cnt=i;
                    for(int j=x1[i]; j<=x2[i]; j++)
                    {
                        if(mp[j][y1[i]]<('a'+i-1))
                        {
                            flag=0;
                            break;
                        }
                    }
                    live[i]=1;
                }
                else
                {
                    flag=0;
                    break;
                }
            }
        }
//    for(int i=1; i<=5; i++)
//        printf("%d %d %d %d
",x1[i],x2[i],y1[i],y2[i]);
        if(flag==0)
            printf("NO
");
        else
        {
            printf("YES
%d
",cnt);
            for(int i=1; i<=cnt; i++)
            {
                if(live[i]==0)
                {
//                    printf("???");
                    for(int j=i+1; j<=26; j++)
                    {
                        if(live[j]==1)
                        {
                            printf("%d %d %d %d
",x1[j],y1[j],x2[j],y2[j]);
                            break;
                        }
                    }
                }
                else
                    printf("%d %d %d %d
",x1[i],y1[i],x2[i],y2[i]);
            }
        }
    }
}