记录编号	203144	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]玛雅游戏	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	3.591 s
提交时间	2015-11-02 17:47:18	内存使用	0.26 MiB

#include<cstdio>
#include<cstring> 

using namespace std;

int n,a[10][10];
bool flag;

class at{
	public :
		int x,y,c;
}cmd[10];

inline void Swap(int &a,int &b){ int c=a;a=b,b=c; }

void down(int,int);

void update()
{
	bool flag[10][10];bool can=0;
	memset(flag,0,sizeof(flag));
	for(int i=0;i<5;i++){
		for(int j=0;j<7;j++){
			if(!a[i][j]) continue;
			for(int k=1;k+i-1<=5;k++){     //水平方向 
				if(a[i][j]!=a[i+k-1][j]||!a[i+k-1][j]){
					if(k>3){
						can=1;
						for(int l=k-1;l>0;l--){
							//a[i+l-1][j]=0; 
							flag[i+l-1][j]=1;
						}
					}
					break;
				}
			}
			for(int k=1;k+j-1<=7;k++){     //竖直方向 
				if(a[i][j]!=a[i][j+k-1]||!a[i][j+k-1]){
					if(k>3){
						can=1;
						for(int l=k-1;l>0;l--){
							//a[i][j+l-1]=0;	
							flag[i][j+l-1]=1;
						}
					}
					break;
				}
			}
		}
	}
	for(int i=0;i<5;i++){
		for(int j=0;j<7;j++){
			if(flag[i][j]) a[i][j]=0;
		}
	}
	for(int i=0;i<5;i++){
		for(int j=5;j>=0;j--){
			if(!a[i][j]&&a[i][j+1]){
				down(i,j);
			}
		}
	}
	if(can) update();
	return;
}

void down(int x,int y)
{
	if(a[x][y]==0){
		while(a[x][y+1]){
			a[x][y]=a[x][y+1];
			y++;
		}
		a[x][y]=0;
	}
}

void right(int x,int y)
{
	if(a[x+1][y]) Swap(a[x+1][y],a[x][y]),update();
	else{
		int t=y-1;
		while(!a[x+1][t]&&t>=0) t--;
		a[x+1][t+1]=a[x][y];
		a[x][y]=0;
		down(x,y);
		update();
	}
}

void left(int x,int y)
{
	if(a[x-1][y]) Swap(a[x-1][y],a[x][y]),update();
	else{
		int t=y-1;
		while(!a[x-1][t]&&t>=0) t--;
		a[x-1][t+1]=a[x][y];
		a[x][y]=0;
		down(x,y);
		update();
	}
}

void dfs(int x)
{
	if(x>n+1) return;
	if(flag) return;
	if(x==n+1){
		for(int i=0;i<5;i++){
			for(int j=0;j<5;j++){
				if(a[i][j]) return;
			}
		}
		flag=1;return;
	}
	int c[10][10];
	memcpy(c,a,sizeof(c));
	for(int i=0;i<5;i++){
		for(int j=0;j<7;j++){
			if(!a[i][j]) continue;
			if(i!=4){
				cmd[x].x=i,cmd[x].y=j;cmd[x].c=1;	
				right(i,j);
				dfs(x+1);
				if(flag) return;
				memcpy(a,c,sizeof(a));
			}
			if(i!=0&&!a[i-1][j]){
				cmd[x].x=i,cmd[x].y=j;cmd[x].c=-1;
				left(i,j);
				dfs(x+1);
				if(flag) return;
				memcpy(a,c,sizeof(a));
			}
		}
	}
	return ;
}

int main()
{
    freopen("mayan.in","r",stdin);
	freopen("mayan.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<5;i++){
		int x;scanf("%d",&x);
		for(int j=0;x!=0;scanf("%d",&x),j++){
			a[i][j]=x;
		}
	}
	dfs(1);
	if(!flag){
		printf("-1");
	}else{
		for(int i=1;i<=n;i++){
			printf("%d %d %d\n",cmd[i].x,cmd[i].y,cmd[i].c);;
		}
	}
	getchar();getchar();
	return 0;
}