记录编号	33952	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]玛雅游戏	最终得分	100
用户昵称	Czb。	是否通过	通过
代码语言	C++	运行时间	2.157 s
提交时间	2011-11-23 19:05:15	内存使用	1.96 MiB

#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;
}