BFS,超级麻烦

推荐A这道模拟方块转换

高高的星空,簇簇闪耀的群星形态万千。一个星座(cluster)是一群连通的星组成的非空连通星系,这里的连通是指水平,垂直或者对角相邻的两个星星。一个星座不能是另一个更大星座的一部分, 星座可以相似(similar)。如果两个星座有相同的形状,而且包括相同数目的星体,那么不管其方向性如何,就算相似。一般而言,星座可能的方向有八个,如图所示。(图片搬运自Luogu Online Judge)

 

 

懒癌了,我就贴上来吧……我用了一个特殊的表来判断是不是相似

详见代码

 

 

#include<cstdio>  
#include<iostream>  
#include<cstring>  
#include<string>  
#include<cmath>  
#include<queue>  
using namespace std;  
  
bool mapx[110][110]={false};  
int xx,yx;  
char cmapx[110][110]={0};  
int L[510][220]={0},R[510][220]={0},alstart=0,arstart=0,blstart=0,brstart=0,alend=210,arend=210,blend=210,brend=210;  
int starnum[510]={0},cmapc[510]={0};  
  
void checkLR(int x,int sl,int el,int sr,int er)  
{  
    printf("L\n");  
    for (int i=sl;i<=el;i++) printf("%d ",L[x][i]);  
    printf("\nR\n");  
    for (int i=sr;i<=er;i++) printf("%d ",R[x][i]);  
    printf("\n\n");  
}  
  
void FindStartEnd(int amap,int bmap)  
{  
    while (L[amap][alstart]==0) alstart++;  
    while (R[amap][arstart]==0) arstart++;  
    while (L[amap][alend]==0) alend--;  
    while (R[amap][arend]==0) arend--;  
    while (L[bmap][blstart]==0) blstart++;  
    while (R[bmap][brstart]==0) brstart++;  
    while (L[bmap][blend]==0) blend--;  
    while (R[bmap][brend]==0) brend--;  
    /*printf("A map L start at : %d end at : %d\n",alstart,alend); 
    printf("A map R start at : %d end at : %d\n",arstart,arend); 
    printf("B map L start at : %d end at : %d\n",blstart,blend); 
    printf("B map R start at : %d end at : %d\n",brstart,brend); 
    checkLR(amap,alstart,alend,arstart,arend); 
    checkLR(bmap,blstart,blend,brstart,brend);*/  
}  
  
bool match(int amap,int bmap,int mode)  
{  
    //find a start  
    alstart=arstart=blstart=brstart=0; alend=arend=blend=brend=210;  
    FindStartEnd(amap,bmap);  
      
    while (alstart<=alend)  
    {  
        switch(mode)  
        {  
        case 0://Normal  
            if (alend-alstart!=blend-blstart) return false;  
            if (L[amap][alstart]!=L[bmap][blstart]) return false;  
            alstart++; blstart++;  
            break;  
        case 1://180  
            if (alend-alstart!=blend-blstart) return false;  
            if (L[amap][alstart]!=L[bmap][blend]) return false;  
            alstart++; blend--;  
            break;  
        case 2://90 R  
            if (alend-alstart!=brend-brstart) return false;   
            if (L[amap][alstart]!=R[bmap][brend]) return false;  
            alstart++; brend--;  
            break;  
        case 3://90 L  
            if (alend-alstart!=brend-brstart) return false;  
            if (L[amap][alstart]!=R[bmap][brstart]) return false;  
            alstart++; brstart++;  
            break;  
        case 4://rev  
            if (alend-alstart!=blend-blstart) return false;  
            if (L[amap][alstart]!=L[bmap][blstart]) return false;  
            alstart++; blstart++;  
            break;  
        case 5://rev+90L  
            if (alend-alstart!=brend-brstart) return false;  
            if (L[amap][alstart]!=R[bmap][brstart]) return false;  
            alstart++; brstart++;  
            break;  
        case 6://rev+90R  
            if (alend-alstart!=brend-brstart) return false;  
            if (L[amap][alstart]!=R[bmap][brend]) return false;  
            alstart++; brend--;  
            break;  
        case 7://rev+180  
            if (alend-alstart!=blend-blstart) return false;  
            if (L[amap][alstart]!=L[bmap][blend]) return false;  
            alstart++; blend--;  
            break;  
        }  
    }  
    while (arstart<=arend)  
    {  
        switch(mode)  
        {  
        case 0://Normal  
            if (arend-arstart!=brend-brstart) return false;  
            if (R[amap][arstart]!=R[bmap][brstart]) return false;  
            arstart++; brstart++;  
            break;  
        case 1://180  
            if (arend-arstart!=brend-brstart) return false;  
            if (R[amap][arstart]!=R[bmap][brend]) return false;  
            arstart++; brend--;  
            break;  
        case 2://90 R  
            if (arend-arstart!=blend-blstart) return false;  
            if (R[amap][arstart]!=L[bmap][blstart]) return false;  
            arstart++; blstart++;  
            break;  
        case 3://90 L  
            if (arend-arstart!=blend-blstart) return false;  
            if (R[amap][arstart]!=L[bmap][blend]) return false;  
            arstart++; blend--;  
            break;  
        case 4://rev  
            if (arend-arstart!=brend-brstart) return false;  
            if (R[amap][arstart]!=R[bmap][brend]) return false;  
            arstart++; brend--;  
            break;  
        case 5://rev+90L  
            if (arend-arstart!=blend-blstart) return false;  
            if (R[amap][arstart]!=L[bmap][blstart]) return false;  
            arstart++; blstart++;  
            break;  
        case 6://rev+90R  
            if (arend-arstart!=blend-blstart) return false;  
            if (R[amap][arstart]!=L[bmap][blend]) return false;  
            arstart++; blend--;  
            break;  
        case 7://rev+180  
            if (arend-arstart!=brend-brstart) return false;  
            if (R[amap][arstart]!=R[bmap][brstart]) return false;  
            arstart++; brstart++;  
            break;  
        }  
    }  
    //printf("Perfect MATCHED!    at mode %d\n",mode);  
    return true;  
}  
  
void Ffill()  //灌水   
{  
    queue<int> quex,quey; //XY轴队列   
    int cache1,cache2,cachex,cachey,fcounter=96,mapcounter=0;  //缓存 染色计数器 子星座计数器   
    int wayx[8]={-1,-1,-1,0,1,1,1,0},wayy[8]={-1,0,1,1,1,0,-1,-1}; //方向表   
    bool matchflag=false;  //匹配标志   
      
    for (int i=0;i<=xx;i++)  
        for (int j=0;j<=yx;j++) if (mapx[i][j]==true)  //瞎灌水   
        {  
            matchflag=false;  
            quex.push(i); quey.push(j); fcounter++; mapcounter++;  
            mapx[i][j]=false; cmapc[mapcounter]=fcounter;  
              
            while (quex.empty()==false)  
            {  
                cachex=quex.front(); cachey=quey.front();  
                quex.pop(); quey.pop();  
                  
                cmapx[cachex][cachey]=(char) fcounter; //把他染色   
                L[mapcounter][cachex-i+105]++; R[mapcounter][cachey-j+105]++;   //建立WZK表   
                starnum[mapcounter]++;  //子星图的星星数目加1   
                  
                for (int w=0;w<=7;w++) if (mapx[cachex+wayx[w]][cachey+wayy[w]]==true)  //瞎灌水x2   
                {  
                    quex.push(cachex+wayx[w]); quey.push(cachey+wayy[w]);  
                    mapx[cachex+wayx[w]][cachey+wayy[w]]=false;  
                }  
            }//Flood Fill ended.  
              
            for (int m=1;m<mapcounter;m++) //寻找之前的子星图   
            {  
                if (matchflag) break;    
                if (starnum[m]==starnum[mapcounter]) /*如果星星数目相同*/  
                   for (int x=0;x<=7;x++) if (match(m,mapcounter,x)==true) //旋转8次判断   
                   {  
                        matchflag=true;  //成功匹配   
                        for (int k=0;k<=xx;k++)  //替换字符   
                        for (int l=0;l<=yx;l++)  
                            if (cmapx[k][l]==(char) fcounter) cmapx[k][l]=(char) cmapc[m];   
                        cmapc[mapcounter]=cmapc[m];  
                        fcounter--;  
                    break;  
                    }  
            }  
        }  
}  
  
int main()  
{  
    char inmap[110]={0};  
    scanf("%d%d",&yx,&xx);  
    for (int i=1;i<=xx;i++)  
    {  
        scanf("%s",inmap);  
        for (int j=0;j<strlen(inmap);j++) if (inmap[j]=='1') mapx[i][j+1]=true; //构建一个星系图   
    }  
      
    Ffill();  //灌一遍水   
      
    for (int i=1;i<=xx;i++)   
    {  
        for (int j=1;j<=yx;j++)  
        {  
            if (cmapx[i][j]!=0) printf("%c",cmapx[i][j]);  
            else printf("0");  
        }  
        printf("\n");  
    }  
    return 0;  
}

 

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.