比赛 防止颓废的小练习v0.2 评测结果 AAAAAAAAAA
题目名称 玛雅游戏 最终得分 100
用户昵称 Kulliu 运行时间 1.954 s
代码语言 C++ 内存使用 74.70 MiB
提交时间 2016-10-18 21:11:51
显示代码纯文本
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cctype>
#include<ctime>
#include<cmath>
#include<queue>
#include<list>
#include<map>
#include<set>
using namespace std;
#define INF 0x7fffffff
int mayan[500000][7][5]={0},f[500000]={0},x[500000]={0},y[500000]={0},c[500000]={0},a[7][5],top=1;
int n;
bool check=0;
void cheak(int p[7][5])
{
    	for(int i=6;i>=0;i--)
    	{
    		for(int j=0;j<5;j++)
    			cout<<p[i][j]<<" ";
    		cout<<endl;
    	}
    	cout<<endl;
}
void swap(int i,int j,int x,int y)
{
    	int t;
    	t=a[i][j];
    	a[i][j]=a[x][y];
    	a[x][y]=t;
}
bool empty(int p[7][5])
{
    	for(int i=0;i<7;i++)
    		for(int j=0;j<5;j++)
    			if(p[i][j]!=0)
    				return 0;
    	return 1;
}
void down()
{
    	for(int i=1;i<7;i++)
    		for(int j=0;j<5;j++)
    			if(a[i][j]!=0)
    			{
    				int k=i-1;
    				while(k>=0&&a[k][j]==0) {swap(k+1,j,k,j);k--;}
    			}
}
void out(int now){
    	if(now==1) return;
        out(f[now]);
    	printf("%d %d %d\n",x[now],y[now],c[now]);
}
bool pan(){
    	int tot[11]={0};
    	for(int i=0;i<7;i++)
    		for(int j=0;j<5;j++)
    			tot[a[i][j]]++;
    	for(int i=1;i<=10;i++)
    		if(tot[i]==1||tot[i]==2) return 0;
    	return 1;
}
bool clear()
{
    	bool now=0;
    	bool bj[7][5]={0};
    	for(int i=0;i<7;i++)
    		for(int j=0;j<5;j++)
    		{
    			if(a[i][j]!=0)
    			{
    			if(j>=2)
    			{
    				int k;
    				for(k=j-1;k<=j;k++)
    					if(a[i][k]!=a[i][k-1]) break;
    				if(k==j+1)
    				{
    					now=1;
    					for(k=j-2;k<=j;k++)
    					bj[i][k]=1;
    				}
    			}
    			if(i>=2)
    			{
    				int k;
    				for(k=i-1;k<=i;k++)
    					if(a[k][j]!=a[k-1][j]) break;
    				if(k==i+1)
    				{
    					now=1;
    					for(k=i-2;k<=i;k++)
    					bj[k][j]=1;
    				}
    			}
    			}
    		}
    		for(int i=0;i<7;i++)
    				for(int j=0;j<5;j++)
    					if(bj[i][j]==1) a[i][j]=0;
    	return now;
}

void haha()
{
    	down();
    	while(clear()) down();
    	return;
}

void dfs(int dep,int fa)
{
    	if(check) return;
    	if(dep>n)
    	{
    		if(empty(mayan[fa]))
    		{
    			check=1;
    			out(fa);
    		}
    		return;
    	}
    	for(int j=0;j<5;j++)
    		for(int i=0;i<7;i++)
    		{
    			if(mayan[fa][i][j]!=0)
    			{
    				memcpy(a,mayan[fa],sizeof(a));
    				if(j!=4)
    				{
    					swap(i,j,i,j+1);
    					haha();
    					if((dep==n||!empty(a))&&pan())
    					{
    						memcpy(mayan[++top],a,sizeof(a));
    						x[top]=j;
    						y[top]=i;
    						c[top]=1;
    						f[top]=fa;
    						dfs(dep+1,top);
    						top--;
    					}
    				}
    				memcpy(a,mayan[fa],sizeof(a));
    				if(j!=0&&a[i][j-1]==0)
    				{
    					
    					swap(i,j,i,j-1);
    					haha();
    					if((dep==n||!empty(a))&&pan())
    					{
    						memcpy(mayan[++top],a,sizeof(a));
    						x[top]=j;
    						y[top]=i;
    						c[top]=-1;
    						f[top]=fa;
    						dfs(dep+1,top);
    						top--;
    					}
    				}
    			}
    		}
}
int main()
{
    	freopen("mayan.in","r",stdin);
    	freopen("mayan.out","w",stdout);
    	scanf("%d",&n);
    	int a;
    	for(int i=0;i<5;i++)
    	{
    		int j=0;
    		while(true)
    		{
    			scanf("%d",&a);
    			if(!a) break;
    			mayan[1][j][i]=a;
    			j++;
    		}
    	}
        dfs(1,1);
    	if(check==0)
    		printf("-1");
    	return 0;
}