【寒假作业】【NOIP2011】Mayan游戏

也是一个鬼得不行的搜索题。。

剪剪枝就完了

【~~代码是我蒯的真的没力气写这种鬼题~~

// <mayan.cpp> - 02/11/16 10:30:45
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
struct T{
	int x,y,ops;
}ans[10];
int st[10][10];
int n;
bool empty(){
	for(int i=0;i<5;i++)
		for(int j=0;j<7;j++)
			if(st[i][j])return false;
	return true;
}
void drop(){
	int num[10][10];
	memset(num,-1,sizeof num);
	for(int x=0;x<5;x++){
		int h=0;
		for(int y=0;y<7;y++)
			if(st[x][y])num[x][h++]=y;
	}
	for(int x=0;x<5;x++)
		for(int y=0;y<7;y++)
			st[x][y]=num[x][y]==-1?0:st[x][num[x][y]];
	return;
}
bool clear(){
	bool flag=0;
	for(int x=0;x<3;x++)
		for(int y=0;y<7;y++)
			if(st[x][y]){
				int x2;
				for(x2=x;x2+1<5&&st[x2+1][y]==st[x][y];x2++);
				if(x2-x>=2){
					int tx;
					for(tx=x;tx<=x2;tx++){
						int Up=y,Dn=y;
						while(Up+1<7&&st[tx][Up+1]==st[x][y])Up++;
						while(Dn-1>=0&&st[tx][Dn-1]==st[x][y]) Dn--;
						if(Up-Dn>=2)
							for(int ty=Dn;ty<=Up;ty++)st[tx][ty]=0;
					}
					for(tx=x;tx<=x2;tx++)st[tx][y]=0;
					flag=1;
				}
			}
	for(int x=0;x<5;x++)
		for(int y=0;y<5;y++)
			if(st[x][y]){
				int y2;
				for(y2=y;y2+1<7&&st[x][y2+1]==st[x][y];y2++);
				if(y2-y>=2){
					for(int ty=y;ty<=y2;ty++){
						int Lf=x,Ri=x;
						while(Lf-1>=0&&st[Lf-1][ty]==st[x][y])Lf--;
						while(Ri+1<7&&st[Ri+1][ty]==st[x][y])Ri++;
						if(Ri-Lf>=2)
							for(int tx=Lf;tx<=Ri;tx++)st[tx][ty]=0;
					}
					for(int ty=y;ty<=y2;ty++)st[x][ty]=0;
					flag=1;
				}
			}
	if(flag)return true;
	else return false;
}
void dfs(int step){
	if(step>n){
		if(empty()){
			for(int i=1;i<=n;i++){
				if(ans[i].ops)printf("%d %d %d\n",ans[i].x+1,ans[i].y,-1);
				else printf("%d %d %d\n",ans[i].x,ans[i].y,1);
			}
			exit(0);
		}
		return;
	}
	int sum[12];
	memset(sum,0,sizeof sum);
	for(int x=0;x<5;x++)
		for(int y=0;y<7;y++)
			sum[st[x][y]]++;
	for(int i=1;i<=10;i++)
		if(sum[i]&&sum[i]<3)return;
	for(int x=0;x<4;x++)
		for(int y=0;y<7;y++)
			if(st[x][y]!=st[x+1][y]){
				ans[step].x=x;
				ans[step].y=y;
				ans[step].ops=(!st[x][y]);
				int temp[10][10];
				memcpy(temp,st,sizeof temp);
				swap(st[x][y],st[x+1][y]);
				drop();
				while(clear())drop();
				dfs(step+1);
				ans[step].x=0;
				ans[step].y=0;
				ans[step].ops=0;
				memcpy(st,temp,sizeof st);
			}
}
int main(){
	freopen("mayan.in","r",stdin);
	freopen("mayan.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<5;i++)
		for(int j=0;;j++){
			st[i][j]=getint();
			if(!st[i][j])break;
		}
	dfs(1);
	printf("-1\n");
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

// <mayan.cpp> - 02/11/16 10:30:45

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

struct T{

int x,y,ops;

}ans[10];

int st[10][10];

int n;

bool empty(){

for(int i=0;i<5;i++)

for(int j=0;j<7;j++)

if(st[i][j])return false;

return true;

}

void drop(){

int num[10][10];

memset(num,-1,sizeof num);

for(int x=0;x<5;x++){

int h=0;

for(int y=0;y<7;y++)

if(st[x][y])num[x][h++]=y;

}

for(int x=0;x<5;x++)

for(int y=0;y<7;y++)

st[x][y]=num[x][y]==-1?0:st[x][num[x][y]];

return;

}

bool clear(){

bool flag=0;

for(int x=0;x<3;x++)

for(int y=0;y<7;y++)

if(st[x][y]){

int x2;

for(x2=x;x2+1<5&&st[x2+1][y]==st[x][y];x2++);

if(x2-x>=2){

int tx;

for(tx=x;tx<=x2;tx++){

int Up=y,Dn=y;

while(Up+1<7&&st[tx][Up+1]==st[x][y])Up++;

while(Dn-1>=0&&st[tx][Dn-1]==st[x][y]) Dn--;

if(Up-Dn>=2)

for(int ty=Dn;ty<=Up;ty++)st[tx][ty]=0;

}

for(tx=x;tx<=x2;tx++)st[tx][y]=0;

flag=1;

}

for(int x=0;x<5;x++)

for(int y=0;y<5;y++)

if(st[x][y]){

int y2;

for(y2=y;y2+1<7&&st[x][y2+1]==st[x][y];y2++);

if(y2-y>=2){

for(int ty=y;ty<=y2;ty++){

int Lf=x,Ri=x;

while(Lf-1>=0&&st[Lf-1][ty]==st[x][y])Lf--;

while(Ri+1<7&&st[Ri+1][ty]==st[x][y])Ri++;

if(Ri-Lf>=2)

for(int tx=Lf;tx<=Ri;tx++)st[tx][ty]=0;

}

for(int ty=y;ty<=y2;ty++)st[x][ty]=0;

flag=1;

}

if(flag)return true;

else return false;

}

void dfs(int step){

if(step>n){

if(empty()){

for(int i=1;i<=n;i++){

if(ans[i].ops)printf("%d %d %d\n",ans[i].x+1,ans[i].y,-1);

else printf("%d %d %d\n",ans[i].x,ans[i].y,1);

}

exit(0);

}

return;

}

int sum[12];

memset(sum,0,sizeof sum);

for(int x=0;x<5;x++)

for(int y=0;y<7;y++)

sum[st[x][y]]++;

for(int i=1;i<=10;i++)

if(sum[i]&&sum[i]<3)return;

for(int x=0;x<4;x++)

for(int y=0;y<7;y++)

if(st[x][y]!=st[x+1][y]){

ans[step].x=x;

ans[step].y=y;

ans[step].ops=(!st[x][y]);

int temp[10][10];

memcpy(temp,st,sizeof temp);

swap(st[x][y],st[x+1][y]);

drop();

while(clear())drop();

dfs(step+1);

ans[step].x=0;

ans[step].y=0;

ans[step].ops=0;

memcpy(st,temp,sizeof st);

}

int main(){

freopen("mayan.in","r",stdin);

freopen("mayan.out","w",stdout);

scanf("%d",&n);

for(int i=0;i<5;i++)

for(int j=0;;j++){

st[i][j]=getint();

if(!st[i][j])break;

}

dfs(1);

printf("-1\n");

return 0;

}