展開圖.c

#include<stdio.h>
#include<stdlib.h>
#define POINT 6
#define SET_M 3
#define WIH 8
#define MAX 25

/*
imatrix,free_imatrix   是抄數值分析課本的函式
主要是讓2D array 比較好傳到別的函式中
pruf_adjm  請參考 https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence

issave 是出問題的函式  他很髒請小心 ^_^

dfs 是把 adjm轉成印出來的答案 很多參數......
*/
int **imatrix(nrl,nrh,ncl,nch)
int nrl,nrh,ncl,nch;
{
    int i,**m;
    m=(int **)malloc((unsigned) (nrh-nrl+1)*sizeof(int*));
    if (!m) printf("allocation failure 1 in imatrix()");
    m -= nrl;
    for(i=nrl; i<=nrh; i++)
    {
        m[i]=(int *)malloc((unsigned) (nch-ncl+1)*sizeof(int));
        if (!m[i]) printf("allocation failure 2 in imatrix()");
        m[i] -= ncl;
    }
    return m;
}
void free_imatrix(m,nrl,nrh,ncl,nch)
int **m;
int nrl,nrh,ncl,nch;
{
    int i;
    for(i=nrh; i>=nrl; i--) free((char*) (m[i]+ncl));
    free((char*) (m+nrl));
}
//end matrix


void pruf_adjm(int *,int **);   //translate
int pfpp(int *);                //pf[]++
int isame(int **,int **,int *);
int issave(int ***s,int **tp,int flg);
void save(int **s,int **tp)
{
    int i,j;
    for(i=0; i<POINT; i++)
        for(j=0; j<POINT; j++)
            s[i][j]=tp[i][j];
}

//void setarray(int *);
void setmtx(int **,int);

//masks:
void xrot(int *);
void yrot(int *);
void zrot(int *);
void mirror(int *);
void remask(int *);
//end masks

void dfs(int **,int **,int,int,int,int,int,int);
//把關係矩陣轉成可以看到的答案

void printans(int **,int);

/*******************************************************/

int main()
{
    int i,j,k,aflag=0;
    int prufer[POINT-1]= {0};
    int **adjmap;
    adjmap=imatrix(0,POINT-1,0,POINT-1);

    int **mp2;           //map2
    mp2=imatrix(0,WIH,0,WIH);

    int **ansmaps[MAX];       //array of (int**)
    for(i=0; i<MAX; i++)
        ansmaps[i]=imatrix(0,POINT-1,0,POINT-1);

    i=0;
    while(pfpp(prufer))
    {
        setmtx(adjmap,POINT);
        pruf_adjm(prufer,adjmap);
        if(adjmap[0][1]==0||adjmap[0][2]==0)
            continue;
        if(adjmap[0][POINT-1]==1||adjmap[1][POINT-2]==1||adjmap[2][POINT-3]==1)
            continue;
        i++;
        if(issave(ansmaps,adjmap,aflag)) /*!!!!!!!!!!!!!!!*/
        save(ansmaps[aflag++],adjmap);

        if(aflag>MAX-1)
        {
            printf("too~many~~anssssss= = ,runs=%d\n\n",i);
            break;
        }
    }

    free_imatrix(adjmap,0,POINT-1,0,POINT-1);

    for(i=0; i<aflag; i++)
    {
        setmtx(mp2,WIH);
        dfs(ansmaps[i],mp2,0,0,SET_M,SET_M,1,2);
        printans(mp2,WIH);
        printf("%d th map\n",i+1);
    }

    printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~\n");

    free_imatrix(mp2,0,WIH,0,WIH);
    for(i=0; i<aflag; i++)
        free_imatrix(ansmaps[i],0,POINT-1,0,POINT-1);

    return 0;
}

/*****************************************************/

int pfpp(int *pf)
{
    int i=0;

    while(pf[POINT-2]==0)
    {
        if(pf[i]<POINT-1)
        {
            pf[i]++;
            return 1;
        }
        else
            pf[i++]=0;
    }
    return 0;
}
void pruf_adjm(int *prf,int **adj)
{
    int i,j;
    int cnt[POINT]= {0};

    for(i=0; i<POINT-2; i++)
        cnt[prf[i]]++;

    for(i=0; i<POINT-2; i++)
    {
        for(j=0; j<POINT; j++)
        {
            if(cnt[j]==0)
            {
                adj[j][prf[i]]=adj[prf[i]][j]=1;
                cnt[j]--;
                cnt[prf[i]]--;
                break;
            }
        }
    }
    for(i=0; i<POINT; i++)
        if (cnt[i]>-1)
            break;
    for(j=POINT-1; j<1; j--)
        if(cnt[j]>-1)
            break;
    adj[i][j]=adj[j][i]=1;
}
int issave(int ***s,int **tp,int flg)
{
    int msk[POINT],i,j;

    while(flg)
    {
        flg--;
        remask(msk);
        for(i=0; i<3; i++)
        {
            zrot(msk);
            if(isame(s[flg],tp,msk))
                return 0;
        }
        zrot(msk);
        xrot(msk);
        if(isame(s[flg],tp,msk))
            return 0;
        for(j=0; j<2; j++)
        {
            for(i=0; i<3; i++)
            {
                yrot(msk);
                if(isame(s[flg],tp,msk))
                    return 0;
            }
            yrot(msk);
            zrot(msk);
            if(isame(s[flg],tp,msk))
                return 0;
            for(i=0; i<3; i++)
            {
                xrot(msk);
                if(isame(s[flg],tp,msk))
                    return 0;
            }
            xrot(msk);
            zrot(msk);
            if(isame(s[flg],tp,msk))
                return 0;
        }
        xrot(msk);
        for(i=0; i<4; i++)
        {
            zrot(msk);
            if(isame(s[flg],tp,msk))
                return 0;
        }
        mirror(msk);
        if(isame(s[flg],tp,msk))
            return 0;
        for(i=0; i<3; i++)
        {
            zrot(msk);
            if(isame(s[flg],tp,msk))
                return 0;
        }
        zrot(msk);
        xrot(msk);
        if(isame(s[flg],tp,msk))
            return 0;
        for(j=0; j<2; j++)
        {
            for(i=0; i<3; i++)
            {
                yrot(msk);
                if(isame(s[flg],tp,msk))
                    return 0;
            }
            yrot(msk);
            zrot(msk);
            if(isame(s[flg],tp,msk))
                return 0;
            for(i=0; i<3; i++)
            {
                xrot(msk);
                if(isame(s[flg],tp,msk))
                    return 0;
            }
            xrot(msk);
            zrot(msk);
            if(isame(s[flg],tp,msk))
                return 0;
        }
        xrot(msk);
        for(i=0; i<4; i++)
        {
            zrot(msk);
            if(isame(s[flg],tp,msk))
                return 0;
        }
    }

    return 1;
}
int isame(int **a,int **bb,int *m)
{
    int i,j;

    for(i=0; i<POINT-1; i++)
    {
        for(j=i+1; j<POINT; j++)
            if(a[i][j]!=bb[m[i]][m[j]])
                return 0;
    }
    return 1;
}
void setmtx(int **mtx,int n)
{
    int i,j;

    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            mtx[i][j]=0;
}
void printans(int **ans,int n)
{
    int i,j;
    for(i=0; i<n; i++)
    {
        for(j=0; j<n; j++)
            if(ans[i][j])
                printf("[%d",ans[i][j]);
            else printf(" .");
        printf("\n");
    }
    printf("----------------------\n");
}
void dfs(int **ans,int **mp2,int chd,int par,int x,int y,int xp,int yp)
{
    int i;
    mp2[x][y]=chd+1;
    for (i=1; i<POINT; i++)
        if (ans[i][chd] && i!= par)
        {
            if(i==xp)
                dfs(ans,mp2,i,chd,x+1,y,POINT-chd-1,yp);
            if(i==yp)
                dfs(ans,mp2,i,chd,x,y+1,xp,POINT-chd-1);
            if(i==(POINT-xp-1))
                dfs(ans,mp2,i,chd,x-1,y,chd,yp);
            if(i==(POINT-yp-1))
                dfs(ans,mp2,i,chd,x,y-1,xp,chd);
        }
    //printf("leaf:i at %d .x,y=%d,%d\n",i,x,y);
}
//int mask[];
void remask(int *m)
{
    int i;
    for(i=0; i<POINT; i++)
        m[i]=i;
}
void xrot(int *m)
{
    int tmp;
    tmp=m[0];
    m[0]=m[1];
    m[1]=m[POINT-1];
    m[POINT-1]=m[POINT-2];
    m[POINT-2]=tmp;
}
void yrot(int *m)
{
    int tmp;
    tmp=m[POINT-1];
    m[POINT-1]=m[2];
    m[2]=m[0];
    m[0]=m[POINT-3];
    m[POINT-3]=tmp;
}
void zrot(int *m)
{
    int tmp,i;
    tmp=m[1];
    for(i=1; i<POINT-2; i++)
        m[i]=m[i+1];
    m[POINT-2]=tmp;
}
void mirror(int *m)
{
    int tmp;
    tmp=m[0];
    m[0]=m[POINT-1];
    m[POINT-1]=tmp;
}
//mask end