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

#include<cstdio>
#include<cstring>

using namespace std;

int n,st[10][10],now[10][10],cnt;

struct Get_Ans{
	int x,y,opt;
}Ans[10],temp_Ans[10],temp_ans[10];

bool check_hl(int x,int y)
{
	if(now[x][y]==now[x-1][y])
		return (now[x-1][y]==now[x-2][y]);
	return false;
}
bool check_lx(int x,int y)
{
	if((now[x][y]==now[x][y-1]))
		return (now[x][y-1]==now[x][y-2]);
	return false;
}

bool Check_tot()
{
	bool del[10][10];int temp_cnt=cnt;memset(del,0,sizeof(del));
	for(int i=0;i<5;i++)for(int j=0;j<7;j++){
		if(i>=2){
			if(!now[i][j])continue;
			if(check_hl(i,j))del[i][j]=del[i-1][j]=del[i-2][j]=1;
		}
		if(j>=2){
			if(!now[i][j])continue;
			if(check_lx(i,j))del[i][j]=del[i][j-1]=del[i][j-2]=1;
		}
	}
	for(int i=0;i<5;i++)for(int j=6;j>=0;j--)if(del[i][j]){
		now[i][j]=0;int temp=j;cnt--;
		while(temp<7){
			now[i][temp]=now[i][temp+1];
			if(!now[i][temp+1])break;temp++;
		}
	}
	if(cnt<temp_cnt)return true;
	return false;
}

void Drag(int x,int y)
{
	now[x][y]^=now[x+1][y];
	now[x+1][y]^=now[x][y];
	now[x][y]^=now[x+1][y];
	while(Check_tot());
}

void Drag_right_empty(int x,int y)
{
	int temp=y;while(!now[x+1][temp-1]&&temp-1>=0)temp--;
	now[x+1][temp]=now[x][y];temp=y;
	while(temp<7){
		now[x][temp]=now[x][temp+1];
		if(!now[x][temp+1])break;temp++;
	}
	while(Check_tot());
}

void Drag_left_empty(int x,int y)
{
	int temp=y;while(!now[x-1][temp-1]&&temp-1>=0)temp--;
	now[x-1][temp]=now[x][y];temp=y;
	while(temp<7){
		now[x][temp]=now[x][temp+1];
		if(!now[x][temp+1])break;temp++;
	}
	while(Check_tot());
}

bool comp()
{
	for(int i=1;i<=n;i++){
		if(Ans[i].x==temp_Ans[i].x){
			if(Ans[i].y==temp_Ans[i].y){
				if(Ans[i].opt==temp_Ans[i].opt)continue;
				else{
					if(Ans[i].opt>temp_Ans[i].opt)return false;
					else return true;
				}
			}
			else{
				if(Ans[i].y>temp_Ans[i].y)return true;
				else return false;
			}
		}
		else{
			if(Ans[i].x<temp_Ans[i].x)return false;
			else return true;
		}
	}
	return false;
}

void dfs(int dth)
{
	if(dth<n&&(!cnt))return;
	if(dth==n){
		if(!cnt){
			if(comp()){
				for(int i=1;i<=dth;i++){
					Ans[i].x=temp_Ans[i].x;
					Ans[i].y=temp_Ans[i].y;
					Ans[i].opt=temp_Ans[i].opt;
				}
			}
		}
		return;
	}
	int temp[10][10],temp_cnt=cnt;
	memcpy(temp,now,sizeof(now));
	memcpy(temp_ans,temp_Ans,sizeof(temp_Ans));
	for(int i=0;i<5;i++){
		for(int j=0;j<7;j++){
			if(!now[i][j])continue;
			if(now[i][j]!=now[i+1][j]){
				if(now[i+1][j]){
					Drag(i,j);temp_Ans[dth+1].x=i;
					temp_Ans[dth+1].y=j;temp_Ans[dth+1].opt=1;
					dfs(dth+1);cnt=temp_cnt;memcpy(now,temp,sizeof(now));
					memcpy(temp_Ans,temp_ans,sizeof(temp_Ans));
				}
				else{
					if(i+1<5){
						Drag_right_empty(i,j);temp_Ans[dth+1].x=i;
						temp_Ans[dth+1].y=j;temp_Ans[dth+1].opt=1;dfs(dth+1);
						cnt=temp_cnt;memcpy(now,temp,sizeof(now));
						memcpy(temp_Ans,temp_ans,sizeof(temp_Ans));
					}
				}
			}
			if(now[i-1][j]||(i-1)<0)continue;
			Drag_left_empty(i,j);temp_Ans[dth+1].x=i;
			temp_Ans[dth+1].y=j;temp_Ans[dth+1].opt=-1;
			dfs(dth+1);cnt=temp_cnt;memcpy(now,temp,sizeof(now));
			memcpy(temp_Ans,temp_ans,sizeof(temp_Ans));
		}
	}
}

int main()
{
    freopen("mayan.in","r",stdin);
	freopen("mayan.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<5;i++){
	    int j=0;scanf("%d",&st[i][j]);
	    now[i][j]=st[i][j];
		while(st[i][j]!=0){
			cnt++;j++;scanf("%d",&st[i][j]);
			now[i][j]=st[i][j];
		}
	}
	for(int i=0;i<=5;i++)Ans[i].x=Ans[i].y=0x2fffffff;
	dfs(0);
	if(Ans[1].opt==0)printf("-1");
	else {
		for(int i=1;i<=n;i++)
			printf("%d %d %d\n",Ans[i].x,Ans[i].y,Ans[i].opt);
	}
}