NOIP2011一試的第三題給我介紹了一個好玩的智力遊戲——Mayan Puzzle。聯賽過後，我從網上下載了這個一夜間變得巨火的遊戲。
在遊戲中，第9關被用來當聯賽那題的說明，第14關就是輸入輸出樣例。
遊戲下載：
英文原版、
漢化版
首先先誇讚一下遊戲的開發人員，動畫效果做的不錯啊！
我在第8關就碰到了難題，一直過不了關，於是就用聯賽時寫的程序試了一下，結果很棒，程序總能找到正確的解決方案！於是從第8關到第45關都是我用程序解出來的～～
先貼上程序吧：
//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
於是我按照程序的“指示”移動方塊，沒想到果然過關了！
