比赛 |
防止颓废的小练习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;
}