题解 P1312 【Mayan游戏】

· · 题解

代码里shadow了I和j，见谅。

按题意安排I,j顺序。

容易发现两个非空块交换可以是左块右移或右块左移，根据题意此时右块左移无意义。

当有一个空块时，非空块的左右移都有意义。

得出剪枝，一个块的左边是非空块时不需要考虑左移。

另一个显然的剪枝，交换两个颜色相同的块没有意义。

由于我不太确定双hash的冲突率是多少，所以我选择了trie来判重。注意状态中同时包含步数和局面。通过改动trie可以得到更强的“相同局面步数不同”的剪枝。做法是在每个叶节点记录到达的最小步数。这样做的空间复杂度会略略提高，但是微乎其微。这种做法我没有尝试。

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::swap;
const int H=7,W=5,MAXN=10;
int n;
struct NODE{
    bool e;
    NODE* ch[11];
    NODE(){memset(ch,0,sizeof(ch));e=0;}
}root;
bool in(int a[H][W],int dep){
    return true;
    NODE* pos=&root;
    if(!pos->ch[dep]) pos->ch[dep]=new NODE();
    pos=pos->ch[dep];
    for(int i=0;i<H;i++) for(int j=0;j<W;j++){
        if(!pos->ch[a[i][j]]) pos->ch[a[i][j]]=new NODE();
        pos=pos->ch[a[i][j]];
    }
    if(!pos->e) return pos->e=1;
    else return false;
}
struct REC{
    int x,y,g;
}rec[MAXN];
bool del[H][W];
void dfs(int bc,int dep,int a[H][W]){//now dep
    if(dep>n){
        if(bc) return;
        for(int i=1;i<=n;i++) printf("%d %d %d\n",rec[i].x,rec[i].y,rec[i].g);
        exit(0);
    }/*
    if(dep){
        printf("\ndep%d\n",dep);
        for(int i=0;i<H;i++,printf("\n")) for(int j=0;j<W;j++) printf("%d ",a[i][j]);
        if(a[5][2]==1&&a[5][3]==4&&a[5][4]==3) {
            getchar();
        }
    }*/
    int tmp[H][W];
    memcpy(tmp,a,sizeof(tmp));
    for(int j=0;j<W;j++) for(int i=H-1;i>=0;i--) for(int dd=1;dd>=-1;dd-=2) if((j+dd<W&&j+dd>=0)&&tmp[i][j]){
         if(tmp[i][j]==tmp[i][j+dd]) continue;
         if(dd==-1&&tmp[i][j-1]) continue;
        memcpy(a,tmp,sizeof(tmp));
        swap(a[i][j],a[i][j+dd]);
        for(int j=0;j<W;j++) for(int i=H-1;i>=0;i--){
            if(a[i][j]) for(int ni=i;ni+1<H&&!a[ni+1][j];ni++) a[ni+1][j]=a[ni][j],a[ni][j]=0;
        }
        int cnt=0,tcnt=0;
        while(1){
            memset(del,0,sizeof(del));
        for(int i=0;i<H;i++) {
            int j=0;
            while(j<W){
                int t;
                for(t=j;t+1<W;){
                    if(a[i][j]&&a[i][j]==a[i][t+1]) t++;
                    else break;
                }
                if(t-j+1>=3) for(int k=j;k<=t;k++) del[i][k]=1;
                j=t+1;
            }
        }
        for(int j=0;j<W;j++) {
            int i=0;
            while(i<H){
                int t;
                for(t=i;t+1<H;){
                    if(a[i][j]&&a[i][j]==a[t+1][j]) t++;
                    else break;
                }
                if(t-i+1>=3) for(int k=i;k<=t;k++) del[k][j]=1;
                i=t+1;
            }
        }
        for(int i=0;i<H;i++) for(int j=0;j<W;j++) cnt+=del[i][j],a[i][j]=del[i][j]?0:a[i][j];
        if(!cnt) break;
        else tcnt+=cnt,cnt=0;
        for(int j=0;j<W;j++) for(int i=H-1;i>=0;i--){
            if(a[i][j]) for(int ni=i;ni+1<H&&!a[ni+1][j];ni++) a[ni+1][j]=a[ni][j],a[ni][j]=0;
        }
        }    
        rec[dep].x=j,rec[dep].y=H-i-1,rec[dep].g=dd;
        if(in(a,dep)) dfs(bc-tcnt,dep+1,a);
    }
}
int a[H][W];
int main(){
    scanf("%d",&n);
    int tot=0;
    for(int j=0;j<5;j++){
        int t,i=H-1;
        scanf("%d",&t);
        while(t){
            a[i][j]=t;
            scanf("%d",&t);
            tot++;
            i--;
        }
    }
    in(a,0);
    dfs(tot,1,a);
    printf("-1");
}