题解 | #[SCOI2009]生日快乐#

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
int N; 
int path[7][4];//操作左为操作步数,右中1 2 3下标分别为 //横坐标 //纵坐标 //操作

struct node{//图形结构体内含方法 
	int mp[6][8],h[6];//mp为图形数组 //h数组表示为各方块列的高度
	//方法1.判断数组是否清空
	inline bool clear(){
      bool pan=true;
      for(int i=1;i<=5;i++){
	  	if(h[i]!=0) { pan=false;break; } //未全部清除 
	  }
        return pan;
	} 
	//方法2 方块的移动
	inline void move(int x,int y,int op){//x,y为坐标 op为操作情况 
		//由于整个图形在数组中是 侧倒状态 op=1 即 x坐标下移 ; op=-1 x坐标上移
		//判断方块移动位置是否为空
		if(h[op+x]<y){//方块所移的目标位置的高度 小于 当前方块高度 
			//换句话说 方块会掉下去
			
			h[op+x]++;//目标位置高度加一//也为方块高度 
			
			mp[op+x][h[op+x]]=mp[x][y]; //方块的转移 
			//之前位置方块的掉落
			for(int i=y;i<=h[x]-1;i++) mp[x][i]=mp[x][i+1];
			//假设 1 2 3 0 4 5 //那么i的范围 1 2 3 [0 4] 5 //0处赋值为 4; 4 处赋值为 5 //变成1 2 3 4 5 '5'
			h[x]--;//保证后续遍历不会计算到 '5' 
		} 
		else swap(mp[x][y],mp[x+op][y]);//交换位置方块都存在直接交换 
	} 
	//方法3 方块消除单次方法(同行或同列有三个或以上 同色方块 //标记->删除->掉落
	inline bool once_clean(){
		
		bool flag=false,vis[6][8];//flag用于判断 是否存在 可消除的方块组//vis 标记可消去方块的坐标位置
		memset(vis,false,sizeof(vis));
		//侧倒后图形的 横向和纵向 的遍历(就是数组 行和列 的遍历)
		//1.横向判断以及标记 
		for(int i=1;i<=5;i++){//!!!!!j++
			for(int j=2;j<=h[i]-1;j++){//例:i行各方块为 1 1 1 2 3 4 //h[i]==6// j的范围 1 [1 1 2 3] 4// 
				if(mp[i][j-1]==mp[i][j]&&mp[i][j]==mp[i][j+1]){
					flag=true;//存在可消除方块组 
					vis[i][j-1]=vis[i][j]=vis[i][j+1]=true;//标记可消除方块组 
				}
			} 
		} 
		//2.纵向判断即标记
		for(int i=2;i<=4;i++){
			int min_h=min(h[i-1],min(h[i],h[i+1]));//取 相邻三行的最短高度
			for(int j=1;j<=min_h;j++){
				if(mp[i-1][j]==mp[i][j]&&mp[i][j]==mp[i+1][j]){
					flag=true;
					vis[i-1][j]=vis[i][j]=vis[i+1][j]=true;//!!!!vis//非mp 
				}
			} 
		} 
		//
		if(!flag) return false;//后续不再进行该方法 once_clean()方法 
		//清除和掉落操作
		for(int i=1;i<=5;i++){
			int t=0;//当前i行的实际长度 //方块实际高度 
			for(int j=1;j<=h[i];j++){
				if(!vis[i][j]){
					mp[i][++t]=mp[i][j];
					if(t!=j) mp[i][j]=0;//方块原位置清除 
				}
				else mp[i][j]=0;//!!!!!!!!!!		
			}//!!h[i]=t;的位置放错 
				h[i]=t;//消去方块后新高
		} 
		return true;//也是当前 flag的值 
	}
	//
	inline void clean_all(){
		
		while(once_clean());//如果可消除 就在一次消除后 继续判断是否消除 
	}
}Mayan;//原始图形 

void dfs(node now,int step){
	//方法截止条件(一般放方法前面)
	if(step==N){
		if(now.clear()){
			for(int i=0;i<step;i++) printf("%d %d %d\n",path[i][1]-1,path[i][2]-1,path[i][3]);
			exit(0);//程序结束 
		}
		return ;
	} 
	//对当前图形进行深度搜索//!!!就是把可以操作的都操作一遍,
	for(int i=1;i<=5;i++){
		for(int j=1;j<=now.h[i];j++){
			//考虑字典序大小 先考虑右移 
			if(i!=5){//前四行考虑只考虑方块下移//也就是原图形中的左边四排考虑右移 
				if(now.mp[i][j]!=now.mp[i+1][j]){//两方块的数值不一样,
					//1.两个位置方块存在,但颜色不一样  2.当前位置有方块, 所转移目标位置没方块
					node nxt;//下一图形
					nxt=now;//该赋值可以更容易理解图形的回溯 
					nxt.move(i,j,1);//
					nxt.clean_all(); 
					path[step][1]=i,path[step][2]=j,path[step][3]=1;
					//对新图像操作
					dfs(nxt,step+1); 
				}
			}
			if(i!=1){
				if(!now.mp[i-1][j]){//只有左边为空才左移 
					node nxt;//下一图形
					nxt=now;//
					nxt.move(i,j,-1);//]
					nxt.clean_all(); 
					path[step][1]=i,path[step][2]=j,path[step][3]=-1;
					//对新图像操作
					dfs(nxt,step+1); 
				}
			}
		}
		
	} 
	return ;
}

inline int read()
{
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}

int main() {
	N=read();//操作数
	for(int i=1;i<=5;i++) {
		int t,j=0;
		while(t=read(),t) Mayan.mp[i][++j]=t;
		Mayan.h[i]=j;
	}
	dfs(Mayan,0);//当前图像Mayan,执行第0+1步操作 
      printf("-1");//如果dfs方法中使用过后,程序未结束,表示不可能全部消除 
	return 0;   
}