题解 P1312 【Mayan游戏】
EnochWenzhou · · 题解
感谢@Most_Hansome神佬提供的思路！！！
很明显是搜索但重点在于怎么去搜。一开始我使用的是广搜因为觉得搜索还要在转移的时候将目前的状态先存下来太麻烦于是打了3000左右字的广搜但是很明显会MLE（我并不想打满分）于是得了20分……
考后觉得太乱于是重写了一遍。深搜的代码异常短只有1600字就A了。although随便造一组数据也能卡掉但我仍认为是一种非常好的方法！！！
原来的广搜（时间不够了连样例都过不了……）
#include<bits/stdc++.h>
using namespace std;
bool f1;
int n,a1,head,tail,f[6][8],A[6][8],u[5]={0,0,0,1,-1},v[5]={0,1,-1,0,0};
struct node{
int gz[6][8],step,ans[6][3],last[3];
}a[1400000];
bool f2;
void dfs(int x,int y,int b){
f[x][y]=1;
for(int i=1;i<=4;i++){
int X=x+u[i],Y=y+v[i];
if(X && Y && X<6 && Y<8 &&
a[b].gz[X][Y]==a[b].gz[x][y] &&
!f[X][Y]) dfs(X,Y,b);
}
}
int QC(int b){
int F=1;
memset(f,0,sizeof(f));
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++){
int co=a[b].gz[i][j];
A[i][j]=0;
if(!co) f[i][j]=1;
if(!f[i][j] && (
(a[b].gz[i][j+1]==co && a[b].gz[i][j+2]==co) ||
(a[b].gz[i][j+1]==co && a[b].gz[i][j-1]==co) ||
(a[b].gz[i][j-1]==co && a[b].gz[i][max(0,j-2)]==co) ||
(a[b].gz[i+1][j]==co && a[b].gz[i+2][j]==co) ||
(a[b].gz[i-1][j]==co && a[b].gz[i+1][j]==co) ||
(a[b].gz[i-1][j]==co && a[b].gz[max(i-2,0)][j]==co)))
dfs(i,j,b),F=0;
}
for(int i=1;i<=5;i++){
int cnt=0;
for(int j=1;j<=7;j++)
if(!f[i][j]) A[i][++cnt]=a[b].gz[i][j];
}
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
a[b].gz[i][j]=A[i][j];
return F;
}
void qc(int b){
while(1) if(QC(b)) return ;
}
int check(int b){
int res=0;
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
if(a[b].gz[i][j]!=0) return 0;
return 1;
}
void kh(node p,int e){
int cnt=0;
for(int i=1;i<=7;i++){
A[0][i]=0;
if(p.gz[e][i]) A[0][++cnt]=p.gz[e][i];
}
for(int i=1;i<=7;i++) p.gz[e][i]=A[0][i];
return ;
}
int main(){
cin>>n;
for(int i=1;i<=5;i++){
int cnt=0;
while(scanf("%d",&a1),a1) a[1].gz[i][++cnt]=a1;
}
head=0,tail=1;
while(head!=tail){
head++;
node now=a[head];
qc(head);
for(int i=1;i<=5;i++){
for(int j=1;j<=7;j++)
cout<<a[head].gz[i][j];
cout<<endl;
}
cout<<endl;
if(check(head)){
for(int i=1;i<=now.step;i++)
printf("%d %d %d\n",
now.ans[i][0]-1,
now.ans[i][1]-1,
now.ans[i][2]);
return 0;
}
for(int i=1;i<=4;i++)
for(int j=1;j<=7;j++)
if(now.gz[i][j] && now.step<n &&
(now.last[0]!=i ||
now.last[1]!=j || now.last[2]!=1)){
node la=now;
swap(la.gz[i][j],la.gz[i+1][j]);
la.ans[++la.step][0]=la.last[0]=i;
la.ans[la.step][1]=la.last[1]=j;
la.ans[la.step][2]=la.last[2]=1;
kh(la,i),kh(la,i+1);
a[++tail]=la;
}
for(int i=2;i<=5;i++)
for(int j=1;j<=7;j++){
if(now.gz[i][j] && now.step<n &&
(now.last[0]!=i ||
now.last[1]!=j || now.last[2]!=-1)){
node la=now;
swap(la.gz[i][j],la.gz[i-1][j]);
la.ans[++la.step][0]=la.last[0]=i;
la.ans[la.step][1]=la.last[1]=j;
la.ans[la.step][2]=la.last[2]=-1;
kh(la,i),kh(la,i-1);
a[++tail]=la;
}
}
}
cout<<-1;
return 0;
}AC：
#include<bits/stdc++.h>
#define F for(int i=1;i<=5;i++)for(int j=1;j<=7;j++)
using namespace std;
int n,a1,p[6][3],fl,a[6][6][8];
int check(int z){
bool hyk,kfs,f[10][10];//hyk表示此时是否还（h）有（y）块（k），若没有为1有则为0，kfs表示 可（k）否（f）删（s）去块
int hls[10],lls[10];//hls为行，lls为列
memset(f,0,sizeof(f));//f数组存的是这个块是否可以被刷掉
do{
hyk=1,kfs=0;
F if(a[z][i][j]){//介于for i=1 to 5与for j=1 to 7实在太多只能使出此下策……
if(f[i][j]){a[z][i][j]=0;continue;}//如果已近在上一次时被刷了，那么将其整成0即可
hyk=0;int jj=j;//如果还有块留着没有被刷就将hyk设为0
while(!a[z][i][jj-1] && jj>1) a[z][i][jj-1]=a[z][i][jj],a[z][i][jj]=0,jj--;//将块下降
}
memset(f,0,sizeof(f));
if(!hyk)
F{
if(!a[z][i][j]) break;
if(a[z][i][j]==a[z][i-1][j]){//处理行
hls[j]++;
if(hls[j]>=3 && a[z][i][j]!=a[z][i+1][j]){//假如在此行的上一个与这个相同那么将连续的个数+1
for(int k=0;k<hls[j];k++) f[i-k][j]=1;//标记被刷的点
kfs=1;//标记还能被刷因此还可以进行下一轮
}
}
else hls[j]=1;
if(a[z][i][j]==a[z][i][j-1]){//处理列，同理
lls[i]++;
if(lls[i]>=3 && a[z][i][j]!=a[z][i][j+1]){
for(int k=0;k<lls[i];k++) f[i][j-k]=1;
kfs=1;
}
}
else lls[i]=1;
}
}while(kfs);//一直可以刷就一直刷下去
return hyk;//判断能否刷完
}
void search(int z){
if(check(z) && z==n){fl=1;return ;}
if(z==n) return ;
for(int i=1;i<5;i++)
for(int j=1;j<=7;j++){//枚举交换方法，因为向右推的优先级更高因此可以先默认为向右，仅当左边为空的时候向左
if(a[z][i][j]==a[z][i+1][j]) continue;//假若两者颜色相同就不必交换
swap(a[z][i][j],a[z][i+1][j]);
for(int I=1;I<=5;I++) for(int J=1;J<=7;J++) a[z+1][I][J]=a[z][I][J];
search(z+1);
if(fl){
p[z][0]=i,p[z][1]=j,p[z][2]=1;
if(!a[z][i+1][j]) p[z][0]++,p[z][2]=-1;// 假如左边为空那么向左
return ;
}
swap(a[z][i][j],a[z][i+1][j]);
}
}
int main(){
cin>>n;
for(int i=1;i<=5;i++){
int cnt=0;
while(scanf("%d",&a1),a1) a[0][i][++cnt]=a1;
}
search(0);
if(fl) for(int i=0;i<n;i++) printf("%d %d %d\n",p[i][0]-1,p[i][1]-1,p[i][2]);
else printf("-1");
return 0;
}