记录编号	181279	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]玛雅游戏	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	3.786 s
提交时间	2015-08-23 20:37:52	内存使用	74.70 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
//i代表y，j代表x
int mayan[500000][7][5]={0};
int f[500000]={0};
int x[500000]={0},y[500000]={0},c[500000]={0};
int a[7][5];
int top=1;
int n;
bool check=0;
void cheak(int p[7][5])
{
	for(int i=6;i>=0;i--)
	{
		for(int j=0;j<5;j++)
			cout<<p[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
}
void swap(int i,int j,int x,int y)
{
	int t;
	t=a[i][j];
	a[i][j]=a[x][y];
	a[x][y]=t;
}
bool empty(int p[7][5])
{
	for(int i=0;i<7;i++)
		for(int j=0;j<5;j++)
			if(p[i][j]!=0)
				return 0;
	return 1;
}
void down()
{
	for(int i=1;i<7;i++)
		for(int j=0;j<5;j++)
			if(a[i][j]!=0)
			{
				int k=i-1;
				while(k>=0&&a[k][j]==0) {swap(k+1,j,k,j);k--;}
			}
}
void out(int now)
{
	if(now==1) return;
    out(f[now]);
	printf("%d %d %d\n",x[now],y[now],c[now]);
}
bool pan()
{
	int tot[11]={0};
	for(int i=0;i<7;i++)
		for(int j=0;j<5;j++)
			tot[a[i][j]]++;
	for(int i=1;i<=10;i++)
		if(tot[i]==1||tot[i]==2) return 0;
	return 1;
}
bool clear()
{
	bool now=0;
	bool bj[7][5]={0};
	for(int i=0;i<7;i++)
		for(int j=0;j<5;j++)
		{
			if(a[i][j]!=0)
			{
			if(j>=2)
			{
				int k;
				for(k=j-1;k<=j;k++)
					if(a[i][k]!=a[i][k-1]) break;
				if(k==j+1)
				{
					now=1;
					for(k=j-2;k<=j;k++)
					bj[i][k]=1;
				}
			}
			if(i>=2)
			{
				int k;
				for(k=i-1;k<=i;k++)
					if(a[k][j]!=a[k-1][j]) break;
				if(k==i+1)
				{
					now=1;
					for(k=i-2;k<=i;k++)
					bj[k][j]=1;
				}
			}
			}
		}
		for(int i=0;i<7;i++)
				for(int j=0;j<5;j++)
					if(bj[i][j]==1) a[i][j]=0;
	return now;
}
void haha()
{
	down();
	while(clear()) down();
	return;
}
void dfs(int dep,int fa)
{
	if(check) return;
	if(dep>n)
	{
		if(empty(mayan[fa]))
		{
			check=1;
			out(fa);
		}
		return;
	}
	for(int j=0;j<5;j++)
		for(int i=0;i<7;i++)
		{
			if(mayan[fa][i][j]!=0)
			{
				memcpy(a,mayan[fa],sizeof(a));
				if(j!=4)
				{
					//cheak(a);
					swap(i,j,i,j+1);
					//cheak(a);
					haha();
					if((dep==n||!empty(a))&&pan())
					{
						memcpy(mayan[++top],a,sizeof(a));
						x[top]=j;
						y[top]=i;
						c[top]=1;
						f[top]=fa;
						dfs(dep+1,top);
						top--;
					}
				}
				memcpy(a,mayan[fa],sizeof(a));
				if(j!=0&&a[i][j-1]==0)
				{
					
					swap(i,j,i,j-1);
					haha();
					if((dep==n||!empty(a))&&pan())
					{
						memcpy(mayan[++top],a,sizeof(a));
						x[top]=j;
						y[top]=i;
						c[top]=-1;
						f[top]=fa;
						dfs(dep+1,top);
						top--;
					}
				}
			}
		}
}
int main()
{
	freopen("mayan.in","r",stdin);
	freopen("mayan.out","w",stdout);
	scanf("%d",&n);
	int a;
	for(int i=0;i<5;i++)
	{
		int j=0;
		while(true)
		{
			scanf("%d",&a);
			if(!a) break;
			mayan[1][j][i]=a;
			j++;
		}
	}
	dfs(1,1);
	if(check==0)
		printf("-1");
	/*for(int i=6;i>=0;i--)
	{
		for(int j=0;j<5;j++)
			cout<<mayan[i][j]<<" ";
		cout<<endl;
	}*/
	return 0;
}