USACO 5.1.2 Starry Night 夜空繁星 starry

This post is written in Chinese. Please consider using Google Translate

这道题很考验人的编程能力。数据不大,但细节要注意。这道题的基本方法就是Floodfill,找到所有的连通块,把全等的连通块标识起来。寻找全等连通块的方法很多,我的方法是把每个连通块散列存储起来。找到一个新的连通块的时候把它和旋转对称变换所得8个图形分别进行散列,然后在哈希表中查找是否出现过。如果出现过,新的连通块与以前的全等。如果没有出现,则找到了一个新的连通块,标识并存储即可。

USER: CmYkRgB123 CmYkRgB123 [cmykrgb1]
TASK: starry
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 3240 KB]
   Test 2: TEST OK [0.011 secs, 3236 KB]
   Test 3: TEST OK [0.000 secs, 3232 KB]
   Test 4: TEST OK [0.000 secs, 3240 KB]
   Test 5: TEST OK [0.022 secs, 3244 KB]

All tests OK.

Your program ('starry') produced all correct answers!  This is your
submission #2 for this problem.  Congratulations!

/*
ID: cmykrgb1
PROG: starry
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 100
#define INF 0x7FFFFFFF

using namespace std;

typedef struct
{
    int x,y;
}point;

class queue
{
private:
    long first,last;
    point list[MAX*MAX+1];
public:
    long size;

    queue()
    {
        reset();
    }

    void reset()
    {
        first=1;
        last=size=0;
    }

    void ins(point k)
    {
        size++;
        list[++last]=k;
    }

    point del()
    {
        size--;
        return list[first++];
    }
};

typedef struct
{
    int width,height;
    char cate;
    bool c[MAX*MAX];
}hashcode;

ifstream fi("starry.in");
ofstream fo("starry.out");

int M,N,hscnt=-1,w=0;
char p[MAX][MAX],newcate='a';
queue Q;
hashcode Ht[30];
point mv[8];

void init()
{
    int i,j;
    fi >> M >> N;
    j=(char)fi.get();
    for (i=0;i<N;i++)
    {
        for (j=0;j<M;j++)
        {
            p[i][j]=fi.get();
        }
        j=(char)fi.get();
    }
    mv[0].x=-1; mv[0].y=-1;
    mv[1].x=-1; mv[1].y=0;
    mv[2].x=-1; mv[2].y=1;
    mv[3].x=0; mv[3].y=-1;
    mv[4].x=0; mv[4].y=1;
    mv[5].x=1; mv[5].y=-1;
    mv[6].x=1; mv[6].y=0;
    mv[7].x=1; mv[7].y=1;
}

void flip(hashcode &h,hashcode &w)
{
    int i,j;
    //左右对称变换
    w.height=h.height;
    w.width=h.width;
    for (i=0;i<=h.height-1;i++)
    {
        for (j=0;j<=h.width-1;j++)
        {
            w.c[(i+1)*h.width-1-j] = h.c[i*h.width+j];
        }
    }
    return;
}

void turn(hashcode &h,hashcode &w)
{
    int i,j;
    //右旋转90度
    w.height=h.width;
    w.width=h.height;
    for (i=0;i<=h.height-1;i++)
    {
        for (j=0;j<=h.width-1;j++)
        {
            w.c[(j+1)*h.height-i-1] = h.c[i*h.width+j];
        }
    }
}

void transform(hashcode * H,int w)
{
    hashcode T;
    if (w==1)
    {
        //左右对称变换
        flip(H[0],H[w]);
        return;
    }
    if (w==2)
    {
        //右旋转90度
        turn(H[0],H[w]);
        return;
    }
    if (w==3)
    {
        //右旋转180度
        turn(H[0],T);
        turn(T,H[w]);
        return;
    }
    if (w==4)
    {
        //右旋转270度
        turn(H[0],H[w]);
        turn(H[w],T);
        turn(T,H[w]);
        return;
    }
    if (w==5)
    {
        //右旋转90度并对称
        turn(H[0],T);
        flip(T,H[w]);
        return;
    }
    if (w==6)
    {
        //右旋转180度并对称
        turn(H[0],H[w]);
        turn(H[w],T);
        flip(T,H[w]);
        return;
    }
    if (w==7)
    {
        //右旋转270度并对称
        turn(H[0],T);
        turn(T,H[w]);
        turn(H[w],T);
        flip(T,H[w]);
        return;
    }
}

int findsame(hashcode &H)
{
    int i,j;
    bool tar;
    for (i=0;i<=hscnt;i++)
    {
        if (Ht[i].height!=H.height || Ht[i].width!=H.width) continue;
        tar=true;
        for (j=0;j<=H.width*H.height-1;j++)
            if (H.c[j]!=Ht[i].c[j])
            {
                tar=false;
                break;
            }
        if (tar)
        {
            return i;
        }
    }
    return -1;
}

void floodfill(int a,int b)
{
    Q.reset();
    point st,cr;
    int i,j,maxx=0,maxy=0,minx=INF,miny=INF;
    st.x=a;st.y=b;
    Q.ins(st);
    if (w==26)
        w=w;
    while (Q.size)
    {
        cr=Q.del();
        if (cr.x<minx) minx=cr.x;
        if (cr.y<miny) miny=cr.y;
        if (cr.x>maxx) maxx=cr.x;
        if (cr.y>maxy) maxy=cr.y;
        p[cr.x][cr.y]='2';
        for (i=0;i<8;i++)
        {
            st.x=cr.x+mv[i].x;
            if (st.x<0 || st.x>N) continue;
            st.y=cr.y+mv[i].y;
            if (st.y<0 || st.y>M) continue;
            if (p[st.x][st.y]=='1')
            {
                Q.ins(st);
                p[st.x][st.y]='2';
            }
        }
    }
    //建立编码
    int k=0;

    hashcode nh[8];
    char cate=0;
    nh[0].width=maxy-miny+1;
    nh[0].height=maxx-minx+1;
    for (i=minx;i<=maxx;i++)
    {
        for (j=miny;j<=maxy;j++)
        {
            if (p[i][j]=='2')
                nh[0].c[k]=true;
            else
                nh[0].c[k]=false;
            k++;
        }
    }
    //寻找全等图形
    for (i=0;i<8;i++)
    {
        if ((k=findsame(nh[i]))!=-1)
        {
            cate=Ht[k].cate;
            break;
        }
        transform(nh,i+1);
    }
    //建立新图形
    if (!cate)
    {
        Ht[++hscnt]=nh[0];
        cate=Ht[hscnt].cate=newcate++;
    }
    //修改原图
    for (i=minx;i<=maxx;i++)
    {
        for (j=miny;j<=maxy;j++)
        {
            if (p[i][j]=='2')
            {
                p[i][j]=cate;
            }
        }
    }
}

void compute()
{
    int i,j;;
    for (i=0;i<N;i++)
    {
        for (j=0;j<M;j++)
        {
            if (p[i][j]=='1')
            {
                floodfill(i,j);
                w++;
                i=i;
            }
        }
    }
}

void print()
{
    int i,j;
    for (i=0;i<N;i++)
    {
        for (j=0;j<M;j++)
        {
            fo << p[i][j];
        }
        fo << endl;
    }
    fi.close();
    fo.close();
}

int main()
{
    init();
    compute();
    print();
    return 0;
}

Related posts