记录编号	188403	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]玛雅游戏	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.714 s
提交时间	2015-09-23 08:28:21	内存使用	0.31 MiB

//n=7 m=5
 
#define MAXN 8UL
 
#define REP for(int i=7;i>0;i--) for(int j=1;j<6;j++)
 
#define LEFT -1
#define RIGHT 1
 
#define MAXR 12UL
 
#include <cstdio>
#include <vector>
 
int r,limited_step,Map_Now[MAXN][MAXN],gs_now[MAXN];
 
bool can_arch;
 
struct Point{
	int x,y,sp;
	inline void Prx(){printf("%d %d %d\n",y-1,7-x,sp);return;}
};
 
std::vector<Point> Move_now;
 
struct Backup{
	int Map[MAXN][MAXN],gs[MAXR];
	inline void Restore(){REP Map_Now[i][j]=Map[i][j];for(int i=1;i<r;i++) gs_now[i]=gs[i];return;}
	inline void Copy(){REP Map[i][j]=Map_Now[i][j];for(int i=1;i<r;i++) gs[i]=gs_now[i];return;}
};
 
inline bool Check_Ok(){for(int i=1;i<=5;i++) if(Map_Now[7][i]) return false;return true;}
inline void Del_Move(){Move_now.pop_back();return;}
inline Point Mk(int x,int y,int k){Point temp;temp.x=x;temp.y=y;temp.sp=k;return temp;}
inline void Add_Move(int x,int y,int mk){Move_now.push_back(Mk(x,y,mk));return;}
inline void Ans_prx(){int s=Move_now.size();for(int i=0;i<s;i++) Move_now[i].Prx();return;}
inline bool Pos_ok(int x,int y){return x>0&&x<8&&y>0&&y<6;}
inline void Push_Down(int x,int y){while(x!=7&&Map_Now[x+1][y]==0) Map_Now[x+1][y]=Map_Now[x][y],Map_Now[x++][y]=0;return;}
inline void Map_Push(int k){for(int i=7;i>0;i--) Push_Down(i,k);return;}
inline bool Sci(){for(int i=1;i<r;i++) if(gs_now[i]>0&&gs_now[i]<3) return true;return false;}
inline bool Killable_X(int x,int y){return Map_Now[x][y+1]==Map_Now[x][y]&&Map_Now[x][y+2]==Map_Now[x][y];}
inline bool Killable_Y(int x,int y){return Map_Now[x+1][y]==Map_Now[x][y]&&Map_Now[x+2][y]==Map_Now[x][y];}
inline void Pm(int p){if(p>r) r=p;return;}
 
inline void Check_Clr(){
	while(true){
		bool killed=false,Kmap[MAXN][MAXN]={0};
		for(int i=7;i>0;i--) for(int j=1;j<4;j++) if(Map_Now[i][j]&&Killable_X(i,j)) killed=true,Kmap[i][j]=Kmap[i][j+1]=Kmap[i][j+2]=true;
		for(int i=5;i>0;i--) for(int j=1;j<6;j++) if(Map_Now[i][j]&&Killable_Y(i,j)) killed=true,Kmap[i][j]=Kmap[i+1][j]=Kmap[i+2][j]=true;
		for(int j=1;j<=5;j++){
			bool Rb=false;
			for(int i=7;i>0&&Map_Now[i][j];i--) if(Kmap[i][j]) Rb=true,--gs_now[Map_Now[i][j]],Map_Now[i][j]=0;
			if(Rb) Map_Push(j);
		}
		if(!killed) break;
	}return;
}
 
inline bool Move(int x,int y,int op){
	if((!Pos_ok(x,y+op))||Map_Now[x][y+op]==Map_Now[x][y]) return false;
	if(Map_Now[x][y+op]){Map_Now[x][y]^=Map_Now[x][y+op];Map_Now[x][y+op]^=Map_Now[x][y];Map_Now[x][y]^=Map_Now[x][y+op];}
	else Map_Now[x][y+op]=Map_Now[x][y],Map_Now[x][y]=0,Map_Push(y),Map_Push(y+op);
	Check_Clr();return true;
}
 
inline void dfs(int step){
	if(Sci()) return;
	if(Check_Ok()){if(step==limited_step) can_arch=true,Ans_prx();return;}
	if(step==limited_step) return;
	Backup backup;backup.Copy();
	for(int j=1;j<=5;j++){
		for(int i=7;i>0&&Map_Now[i][j];i--){
			if(Move(i,j,RIGHT)) Add_Move(i,j,RIGHT),dfs(step+1),backup.Restore(),Del_Move();
			if(can_arch) return;
			if((!Map_Now[i][j-1])&&Move(i,j,LEFT) ) Add_Move(i,j,LEFT ),dfs(step+1),backup.Restore(),Del_Move();
			if(can_arch) return;
		}
	}
	return;
}
 
int main(){
	freopen("mayan.in","r",stdin);freopen("mayan.out","w",stdout);
	scanf("%d",&limited_step);
	for(int i=1,s,j=7;i<=5;i++,j=7) while(scanf("%d",&s)&&s) Map_Now[j--][i]=s,Pm(s),++gs_now[s];
	r++;dfs(0);if(!can_arch) puts("-1");
	return 0;
}