luoguP1312 Mayan游戏 题解(NOIP2011)

luoguP1312 Mayan游戏 题目

#include<bits/stdc++.h>
#define ll long long
#define rg register
#define il inline
#define inf 1<<30;
using namespace std; int a[][],b[][][];
int tmp[][];
int way[][];
int n,ans,maxn; il ll gi()
{
ll x=,o=;
char ch;ch=getchar();
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') o=-,ch=getchar();
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*o;
}
il void input()
{
n=gi();
for(int i=;i<=;i++)
{
int tmp=gi(),p=;
while(tmp)
a[p--][i]=tmp,tmp=gi();
a[][i]=;
}
}
il void print(int a[][])
{
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
cout<<a[i][j];
cout<<endl;
}
}
il void drop(int y)
{
int p=;
for(int i=;i>=;i--)
{
if(a[i][y]!=)
{
p=i+;
while(a[p][y]==)
p++;
if(p==i+) continue;
p-=;
a[p][y]=a[i][y];
a[i][y]=;
}
}
}
il int del(int i,int j,int deti,int detj)
{
int fi=i,fj=j,s=;
while()
{
i+=deti;j+=detj;
if(i==||i==||j==||j==) break;
if(tmp[i][j]!=tmp[fi][fj]) break;
s++;
if(s==) break;
}
i=fi;j=fj;
while()
{
i-=deti;j-=detj;
if(i==||i==||j==||j==) break;
if(tmp[i][j]!=tmp[fi][fj]) break;
s++;
if(s==) break;
}
if(s>=)
{
a[fi][fj]=;
return ;
}
return ;
}
il int delet()
{
int flag=;
for(int i=;i>=;i--)
for(int j=;j<=;j++)
tmp[i][j]=a[i][j];
for(int i=;i>=;i--)
for(int j=;j<=;j++)
{
if(a[i][j]==) continue;
if(del(i,j,,)) flag=;
if(del(i,j,,)) flag=;
}
for(int i=;i<=;i++)drop(i);
return flag;
}
il void move(int x,int y,int mode)
{
swap(a[x][y],a[x][y+mode]);
drop(y);
drop(y+mode);
while(delet());
}
il bool check(int b[][])
{
for(int i=;i>=;i--)
for(int j=;j<=;j++)
{
if(a[i][j]!=)
return ;
}
return ;
}
il void reset(int k)
{
for(int l=;l<=;l++)
for(int r=;r<=;r++)
a[l][r]=b[k][l][r];
}
il void copy(int k)
{
for(int l=;l<=;l++)
for(int r=;r<=;r++)
b[k+][l][r]=a[l][r];
}
il void dfs(int k)
{
if(k>n)
{
if(check(b[k]))
{
ans=;
for(int i=;i<k;i++)
{
for(int j=;j<=;j++)
cout<<way[i][j]<<' ';
cout<<endl;
}
}
return;
}
if(ans) return;
for(int j=;j<=;j++)
{
for(int i=;i>=;i--)
{
reset(k);
if(a[i][j]==) continue;
if(j!=&&a[i][j+]!=a[i][j])
{
way[k][]=j-;
way[k][]=-i;
way[k][]=;
move(i,j,);
copy(k);
dfs(k+);
}
if(ans) return;
reset(k);
if(j!=&&a[i][j-]==)
{
way[k][]=j-;
way[k][]=-i;
way[k][]=-;
move(i,j,-);
copy(k);
dfs(k+);
}
if(ans) return;
}
}
} int main()
{
input();
for(int i=;i<=;i++)
for(int j=;j<=;j++)
b[][i][j]=a[i][j];
dfs();
if(!ans) cout<<"-1"<<endl;
return ;
}
上一篇:学习SQLite之路(四)


下一篇:NOIP2011 Mayan游戏