题解 P1312 【Mayan游戏】

· · 题解

因为没有实名验证，发不了讨论，所以索性发一篇题解。由于自己在这道题上卡了2天，所以犯了各种各样的错误。

首先讲思路，其实和楼下差不多，就是可以换就换，剪枝掉左右一样的，在左面但是已经有块的（因为已经换过了）。

全wa自然不用说，回去重改。只拿10分的，看看自己的消除板块是否有问题。

20分的，看看自己的x轴和y轴是否颠倒。

最重要的地方来了，如果你有5个TLE！！那么你犯了一个可能一星期都查不出来的错误！！那就是最后的判断过程，代码给注释。

在测数据时，如果你也用dev c++如果程序没结果不一定是出错，可以等一等。。。。。。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define in(x) x=read()
int a[10][10];
int read(){
    int num=0;
    char c;
    int flag=1;
    while((c=getchar())==' '||c=='\n'||c=='\r');
    if(c=='-')flag=-1;
    else num=c-'0';
    while(isdigit(c=getchar()))num=num*10+(c-'0');
    return num;

}//由于数据过小，其实没必要读入优化

int n;
int ans1[20],ans2[20],ans3[20];//方向 x y 
int cnt=0;
void remove(){
  for (int i=1;i<=5;++i)
        for (int j=1;j<=7;++j)
        {
            int x=i,y=j;
            while (a[x][y]!=0&&a[x][y-1]==0&&y-1>=1)
            {
                swap(a[x][y],a[x][y-1]);
                --y;
            }

}//降下来！

        int flag=1;
        int c[10][10];
    //    memset(c,0,sizeof(c));另类的储存方法 
        //for(int ii=1;ii<=5;ii++)
    //    for(int jj=1;jj<=7;jj++)
        //c[ii][jj]=a[ii][jj]; 
        memcpy(c,a,sizeof(c));//我们储存一个备份，如果不储存就要另判4个及以上的块 
    for(int i=1;i<=5;i++)
    for(int j=1;j<=7;j++){
        if(c[i][j]){//如果是第四个，那么前面的只是重复的赋了一个0，如果不储存备份，由于a已经修改，第四个就不会被判出 
            if(c[i][j+1]==c[i][j]&&c[i][j-1]==c[i][j]){
                a[i][j]=0;
                a[i][j-1]=0;
                a[i][j+1]=0;
                flag=0;
            }
            if(c[i][j]==c[i-1][j]&&c[i][j]==c[i+1][j]){//这个是相当于是x轴的 消除 
                  a[i][j]=0;
                a[i-1][j]=0;
                a[i+1][j]=0;
            flag=0;
            }
        }
    }
    if(!flag)
        remove();//消除了以后，自然还会有再次需要消除的块 
}
bool judge(){//消除 
    bool flag=1;
    for(int i=1;i<=5;i++){
        if(a[i][1])flag=false;
    }
    return flag;
}
bool dfs(int step){
    if(step>n){
        return 0;
    }
    if(step==n){
        //这里是最重要的地方，如果你写的是if（setp==n&&judge（））那你的不可行的解就会多走一边！ 
        if(judge())return 1;
        return 0;
    }
    int b[10][10];
    memcpy(b,a,sizeof(b));
    for(int i=1;i<=5;i++){
        for(int j=1;j<=7;j++){
            if(a[i][j]){
                if(i!=5&&a[i][j]!=a[i+1][j]){//边界，以及同颜色 向右走 
                     swap(a[i][j],a[i+1][j]);
                    remove();
                    if(dfs(step+1)){//我的代码是有回溯的，也可以没有回溯过程，直接输出，但是我觉得这样更好理解； 
                        ans1[++cnt]=1;
                        ans2[cnt]=i-1;
                        ans3[cnt]=j-1;
                        return 1; 
                    }
          memcpy(a,b,sizeof(a));
                 //vis1[i]=0;
                }
                 if(i!=1&&a[i-1][j]==0){//左走 
                    swap(a[i][j],a[i-1][j]);
                    remove();
                    if(dfs(step+1)){
                        ans1[++cnt]=-1;
                        ans2[cnt]=i-1;
                        ans3[cnt]=j-1;
                        return 1;
                    }
            memcpy(a,b,sizeof(a));
                }
            }
        }
    }
 return 0;
}
int main(){
    in(n);
    memset(a,0,sizeof(a));
   for(int i=1;i<=5;i++){
        int x;
        in(x);
        int j=1;
        while(x){
            a[i][j++]=x;
            in(x);
        }
    }    dfs(0);
    for(int i=cnt;i>=1;i--){
        printf("%d %d %d\n",ans2[i],ans3[i],ans1[i]);//回溯过程是自低向上，所以要倒着输出 
    }
    if(cnt==0)printf("-1");
}