记录编号	73800	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]玛雅游戏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.528 s
提交时间	2013-10-22 22:37:25	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
#include<vector>
using namespace std;
const int SL=7,SR=5;//7行5列
//字典序为:方块从左到右,从下到上,字典序先右后左(右为1)
//本程序中,一般(i,j)表示上起第i行,左起第j列,从1开始编号
void swap(int &a,int &b){
	int c;
	c=a,a=b,b=c;
}
int max_opn;
class BOARD{
public:
	short s[SL+1][SR+1];//0表示空,整数表示方块
	int numd;//方块个数
	int opn;//操作次数
	bool empty(void){return numd==0;}
	BOARD(){memset(s,0,sizeof(s));numd=opn=0;}
	void output(void){
		cout<<"方块个数:"<<numd<<endl;
		for(int i=1;i<=SL;i++){
			for(int j=1;j<=SR;j++){
				cout<<s[i][j]<<" ";
			}
			cout<<endl;
		}
	}
	void row_fall(int);
	void bring_G(void);
	bool line_three_remove(int);
	bool row_three_remove(int);
	bool three_remove(void);
	void simulate_change(void);
	void move_diamond(int,int,int);
};
void BOARD::row_fall(int x){//第x列下落
	int nowe=SL;
	while(nowe>=1&&s[nowe][x]) nowe--;
	if(nowe==0) return;
	int j;
	for(j=nowe-1;j>=1;j--){
		if(s[j][x]){//此处非空
			s[nowe][x]=s[j][x];
			s[j][x]=0;
			nowe--;
		}
	}
}
void BOARD::bring_G(void){//下落
	int i;
	for(i=1;i<=SR;i++) row_fall(i);
}
bool be_removed[SL+1][SR+1]={0};//若(i,j)被消除则该处为true
bool BOARD::line_three_remove(int x){//对第x行进行三消,标记于be_removed中,若有可消除方块则返回true
	int start=1,j,k;
	int nowlen;
	bool flag=false;
	for(j=1;j<=SR;j++){
		if(j==SR||j<SR&&s[x][j+1]!=s[x][j]){//一个颜色块结束
			nowlen=j-start+1;
			if(s[x][start]&&nowlen>=3){//满足消除条件
				flag=true;
				for(k=start;k<=j;k++) be_removed[x][k]=true;
			}
			start=j+1;
		}
	}
	return flag;
}
bool BOARD::row_three_remove(int y){//对第y列进行三消,标记于be_removed中,若有可消除方块则返回true
	int start=1,i,k;
	int nowlen;
	bool flag=false;
	for(i=1;i<=SL;i++){
		if(i==SL||s[i+1][y]!=s[i][y]){//一个颜色块结束
			nowlen=i-start+1;
			if(s[start][y]&&nowlen>=3){//满足消除条件
				flag=true;
				for(k=start;k<=i;k++) be_removed[k][y]=true;
			}
			start=i+1;
		}
	}
	return flag;
}
bool BOARD::three_remove(void){//仅作三消,不进行随后的下落,若有可消除方块则返回true,否则false
	memset(be_removed,0,sizeof(be_removed));
	int i,j;
	bool flag=false;
	for(i=1;i<=SL;i++){//尝试第i行
		if(line_three_remove(i)) flag=true;
	}
	for(j=1;j<=SR;j++){//尝试第j列
		if(row_three_remove(j)) flag=true;
	}
	if(!flag) return false;
	for(i=1;i<=SL;i++){
		for(j=1;j<=SR;j++){
			if(be_removed[i][j]){
				s[i][j]=0;
				numd--;
			}
		}
	}
	return true;
}
void BOARD::simulate_change(void){//对一个一开始就"坐实"的棋盘模拟接下来的所有消除变化直到其停止
	while(three_remove()){
		bring_G();
	}
}
void BOARD::move_diamond(int x,int y,int dr){//移动(x,y),方向dr所描述的方块并模拟之后的一切影响
	int nx,ny;
	nx=x;
	ny=y+dr;
	if(s[nx][ny]){
		swap(s[nx][ny],s[x][y]);
	}
	else{
		swap(s[nx][ny],s[x][y]);
		row_fall(y);
		row_fall(ny);
	}
	simulate_change();
}
class FAT{//这个类表示链表中的"父指针",存放:父亲于队列中的位置和父亲到本节点的操作
public:
	int pos;//父节点在队中位置
	int x,y,g;//此三者是本程序中的特别定义,输出时要予以转换
	void question_output(void){
		cout<<y-1<<" ";
		cout<<SL-x<<" ";
		cout<<g<<endl;
	}
	void output(void){cout<<x<<" "<<y<<" "<<g<<endl;}
};
vector<pair<BOARD,FAT> > Q;
deque<FAT> ans_seq;//答案的操作序列
void get_ans(int x){//自Q[x]始,记录答案序列
	while(x!=0){
		ans_seq.push_front(Q[x].second);
		x=Q[x].second.pos;
	}
}
void answer_question(int x){
	get_ans(x);
	int i;
	for(i=0;i<ans_seq.size();i++) ans_seq[i].question_output();
}
void BFS(void){//绕了一大圈才写到BFS= =
	int tot;
	#define nowb Q[tot].first
	int i,j;
	BOARD atp;//after operation
	FAT last;
	for(tot=0;tot<Q.size();tot++){
		if(nowb.opn>=max_opn) continue;//无法继续进行
		for(j=1;j<=SR;j++){
			for(i=SL;i>=1;i--){
				if(nowb.s[i][j]==0) continue;
				if(j<SR&&nowb.s[i][j]!=nowb.s[i][j+1]){
					atp=nowb;atp.move_diamond(i,j,1);atp.opn++;
					if(atp.opn<max_opn||atp.empty()){
						last.pos=tot;last.x=i,last.y=j,last.g=1;Q.push_back(make_pair(atp,last));
						if(atp.empty()){
							answer_question(Q.size()-1);
							return;
						}
					}
				}
				if(j>1&&nowb.s[i][j-1]==0){
					atp=nowb;atp.move_diamond(i,j,-1);atp.opn++;
					if(atp.opn<max_opn||atp.empty()){
						last.pos=tot;last.x=i,last.y=j,last.g=-1;Q.push_back(make_pair(atp,last));
						if(atp.empty()){
							answer_question(Q.size()-1);
							return;
						}
					}
				}
			}
		}
	}
	printf("-1\n");
}
BOARD orib;
void init(void){
	scanf("%d",&max_opn);
	int j,i,a;
	for(j=1;j<=SR;j++){
		i=SL;
		do{
			scanf("%d",&a);
			if(a){
				orib.s[i][j]=a;
				orib.numd++;
			}
			i--;
		}while(a!=0);
	}
	FAT temp;
	orib.opn=0;
	Q.push_back(make_pair(orib,temp));
}
int main(){
	freopen("mayan.in","r",stdin);
	freopen("mayan.out","w",stdout);
	init();
	BFS();
	return 0;
}