NOIP2011_Day1 mayan:用程序解決mayan puzzle遊戲

NOIP2011一試的第三題給我介紹了一個好玩的智力遊戲——Mayan Puzzle。聯賽過後，我從網上下載了這個一夜間變得巨火的遊戲。

在遊戲中，第9關被用來當聯賽那題的說明，第14關就是輸入輸出樣例。

遊戲下載：英文原版、漢化版

首先先誇讚一下遊戲的開發人員，動畫效果做的不錯啊！

我在第8關就碰到了難題，一直過不了關，於是就用聯賽時寫的程序試了一下，結果很棒，程序總能找到正確的解決方案！於是從第8關到第45關都是我用程序解出來的～～

先貼上程序吧：

C++语言: Codee#24246

//NOIP2011-Senior-mayan
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct aaa
{
    int t[6];
    int c[6][8];
    aaa()
    {
        memset(t,0,sizeof(t));
        memset(c,0,sizeof(c));
    }
};

int n,ans[6][3];

bool flag,b[6][8];

aaa solve(aaa g)
{
    aaa h;
    int i,j;
    for(i=1;i<=5;i++)
    {
        for(j=1;j<=g.t[i];j++)
        {
            if(g.c[i][j]&&!b[i][j])
            {
                h.t[i]++;
                h.c[i][h.t[i]]=g.c[i][j];
            }
        }
    }
    return h;
}

aaa clear(aaa g)
{
    int i,j;
    aaa h;
    flag=false;
    memset(b,0,sizeof(b));
    for(i=1;i<=5;i++)
    {
        for(j=1;j<=g.t[i];j++)
        {
            if(i<=3)
            {
                if(g.c[i][j]==g.c[i+1][j]&&g.c[i][j]==g.c[i+2][j])
                {
                    b[i][j]=b[i+1][j]=b[i+2][j]=true;
                    flag=true;
                }
            }
            if(j<=g.t[i]-2)
            {
                if(g.c[i][j]==g.c[i][j+1]&&g.c[i][j]==g.c[i][j+2])
                {
                    b[i][j]=b[i][j+1]=b[i][j+2]=true;
                    flag=true;
                }
            }
        }
    }
    if(flag)
    {
        h=solve(g);
        return clear(h);
    }
    else
    {
        return g;
    }
}

void output()
{
    freopen("mayan.out","w",stdout);
    int i;
    for(i=1;i<=n;i++)
    {
        printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
    }
    exit(0);
}

void dfs(aaa g,int k)
{
    int i,j,l;
    aaa h;
    flag=true;
    for(i=1;i<=5;i++)
    {
        if(g.t[i])
        {
            flag=false;
            break;
        }
    }
    if(flag)
    {
        if(k>n)
        {
            output();
        }
        else
        {
            return;
        }
    }
    if(k>n)
    {
        return;
    }
    for(i=1;i<=5;i++)
    {
        for(j=1;j<=g.t[i];j++)
        {
            if(i<5)
            {
                if(j>g.t[i+1])
                {
                    h=g;
                    h.t[i+1]++;
                    h.c[i+1][h.t[i+1]]=h.c[i][j];
                    h.c[i][j]=0;
                    h.t[i]--;
                    for(l=j;l<=h.t[i];l++)
                    {
                        h.c[i][l]=h.c[i][l+1];
                    }
                    h=clear(h);
                    ans[k][0]=i-1;
                    ans[k][1]=j-1;
                    ans[k][2]=1;
                    dfs(h,k+1);
                }
                else
                {
                    h=g;
                    l=h.c[i][j];
                    h.c[i][j]=h.c[i+1][j];
                    h.c[i+1][j]=l;
                    h=clear(h);
                    ans[k][0]=i-1;
                    ans[k][1]=j-1;
                    ans[k][2]=1;
                    dfs(h,k+1);
                }
            }
            if(i>1)
            {
                if(j>g.t[i-1])
                {
                    h=g;
                    h.t[i-1]++;
                    h.c[i-1][h.t[i-1]]=h.c[i][j];
                    h.c[i][j]=0;
                    h.t[i]--;
                    for(l=j;l<=h.t[i];l++)
                    {
                        h.c[i][l]=h.c[i][l+1];
                    }
                    h=clear(h);
                    ans[k][0]=i-1;
                    ans[k][1]=j-1;
                    ans[k][2]=-1;
                    dfs(h,k+1);
                }
            }
        }
    }
}

int main()
{
    freopen("mayan.in","r",stdin);
    freopen("mayan.out","w",stdout);
    int i,j;
    aaa g;
    scanf("%d",&n);
    for(i=1;i<=5;i++)
    {
        scanf("%d",&j);
        while(j)
        {
            g.t[i]++;
            g.c[i][g.t[i]]=j;
            scanf("%d",&j);
        }
    }
    dfs(g,1);
    printf("-1\n");
    return 0;
}

比如第10關，把它轉換為程序的輸入文件就是這樣：
mayan.in
3
1 2 2 0
2 0
1 0
3 1 3 0
1 3 1 0

運行程序，輸出文件是：
mayan.out
0 0 1
3 2 1
3 0 1

於是我按照程序的“指示”移動方塊，沒想到果然過關了！