记录编号	442677	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]玛雅游戏	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	2.838 s
提交时间	2017-08-28 08:46:40	内存使用	0.31 MiB

#include<bits/stdc++.h>/*注意：
a) 如果同时有多组方块满足消除条件，几组方块会同时被消除（例如下面图4，三个颜色为1 的方块和三个颜色为2 的方块会同时被消除
，最后剩下一个颜色为2 的方块）。
b) 当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会
被同时消除（例如下面图5 所示的情形，5 个方块会同时被消除）。
任一时刻，如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块，则它们将立即被消除（参见图1 到图3）。*/
using namespace std;
int n;
struct pic{
	int a[10][10],num[11],boo[10][10];
	void read(){
		memset(a,0,sizeof(a));
		for(int i=1;i<=5;i++){
			int o=0;
			int x;
			while(scanf("%d",&x)){
				if(!x)break;
				a[i][++o]=x;
			}
		}
	}
	void get(pic b){
		memset(a,0,sizeof(a));
		for(int i=1;i<=5;i++){
			for(int j=1;j<=7;j++)
			a[i][j]=b.a[i][j];
		}
	}
	void fall(){
		for(int i=1;i<=5;i++){
			for(int j=2;j<=7;j++){
				int o=j;
				while(a[i][o]&&!a[i][o-1]&&o-1>0){
					a[i][o-1]=a[i][o];
					a[i][o]=0;
					o--;
				}
			}
		}
	}
	bool judge(){
		for(int i=1;i<=5;i++)
		for(int j=1;j<=7;j++)
		if(a[i][j])return 0;
		return 1;
	}
	bool xiao(){
		memset(num,0,sizeof(num));
		memset(boo,0,sizeof(boo));
		int book=0;
		for(int i=1;i<=5;i++)
		for(int j=1;j<=7;j++)
		num[a[i][j]]++;
		for(int i=1;i<=5;i++){
			for(int j=1;j<=5;j++){
				if(!a[i][j])continue;
				if(num[a[i][j]]<3)continue;
				int o1=j-1,o2=j+1,o3=i-1,o4=i+1;
				while(a[i][o1]==a[i][j])o1--;
				while(a[i][o2]==a[i][j])o2++;
				while(a[o3][j]==a[i][j])o3--;
				while(a[o4][j]==a[i][j])o4++;
				if(o2-o1>3){
					for(int k=o1+1;k<o2;k++){
						boo[i][k]=1;
					}
					book=1;
				}
				if(o4-o3>3){//开始没看清题目啊！！！应该给被消的打上标记最后一起消，不然先消的话会造成有些有共用块的没法消了 
					for(int k=o3+1;k<o4;k++){//还有竖着两个横着三个竖着的那个是不会消的 
						boo[k][j]=1;
					}
					book=1;
				}
			}
		}
		for(int i=1;i<=5;i++)
		for(int j=1;j<=7;j++)
		if(boo[i][j])a[i][j]=0;
		return book;
	}
};
struct step{
	int x,y,to;
	step(){}
	step(int a,int b,int c){
		x=a;
		y=b;
		to=c;
	}
};
int turkey;
stack<step>S;
stack<step>S2;
void dfs(pic a,int t){
	if(t>n)return ;
	if(turkey)
	return ;
	if(t==n){
	/*	for(int i=1;i<=5;i++){
			for(int j=1;j<=7;j++)
			cout<<a.a[i][j]<<" ";
			cout<<endl;
		}
		system("pause");*/
		if(a.judge()){
			while(!S.empty()){
				step u=S.top();
				S.pop();
				S2.push(u);
			}
			while(!S2.empty()){
				step u=S2.top();
				S2.pop();
				cout<<u.x-1<<" "<<u.y-1<<" "<<u.to<<endl;
			}
			turkey=1;
		}
		else
		return ;
	}
	for(int i=1;i<=5;i++){
		for(int j=1;j<=7;j++){
			if(!a.a[i][j])continue;
			if(i+1<=5){
				pic m;
				m.get(a);
				swap(m.a[i][j],m.a[i+1][j]);
				m.fall();
				while(m.xiao()){
					m.fall();
				}
				step p(i,j,1);
				S.push(p);
				dfs(m,t+1);
				if(!S.empty())//一定要加！！！不然找到结果之后S已经空了，再pop就出事了 
				S.pop();
			}
			if(i-1>=1&&!a.a[i-1][j]){
				pic m;
				m.get(a);
				swap(m.a[i][j],m.a[i-1][j]);
				m.fall();
				while(m.xiao()){
					m.fall();
				}
				step p(i,j,-1);
				S.push(p);
				dfs(m,t+1);
				if(!S.empty())
				S.pop();
			}
		}
	}
}
int main()
{
	freopen("mayan.in","r",stdin);
	freopen("mayan.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d",&n);
	pic a;
	a.read();
	dfs(a,0);
	if(!turkey)
	cout<<-1;
	return 0;
}