题目描述

Mayan puzzle是最近流行起来的一个游戏。游戏界面是一个7行5列的棋盘，上面堆放着一些方块，方块不能悬空堆放，即方块必须放在最下面一行，或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块，消除方块的规则如下：

1、每步移动可以且仅可以沿横向（即向左或向右）拖动某一方块一格：当拖动这一方块时，如果拖动后到达的位置（以下称目标位置）也有方块，那么这两个方块将交换位置（参见输入输出样例说明中的图6到图7）；如果目标位置上没有方块，那么被拖动的方块将从原来的竖列中抽出，并从目标位置上掉落（直到不悬空，参见下面图1和图2）；
2、任一时刻，如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块，则它们将立即被消除（参见图1到图3）。
注意：
a)如果同时有多组方块满足消除条件，几组方块会同时被消除（例如下面图4，三个颜色为1的方块和三个颜色为2的方块会同时被消除，最后剩下一个颜色为2的方 块）。
b)当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会被同时消除（例如下面图5所示的情形，5个方块会同时被消除）。

3、方块消除之后，消除位置之上的方块将掉落，掉落后可能会引起新的方块消除。注意：掉落的过程中将不会有方块的消除。
上面图1到图3给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为（0, 0），将位于（3, 3）的方块向左移动之后，游戏界面从图1变成图2所示的状态，此时在一竖列上有连续三块颜色为4的方块，满足消除条件，消除连续3块颜色为4的方块后，上方的颜色为3的方块掉落，形成图3所示的局面。

输入描述:

第一行为一个正整数n，表示要求游戏通关的步数。
接下来的5行，描述7*5的游戏界面。每行若干个整数，每两个整数之间用一个空格隔开，每行以一个0结束，自下向上表示每竖列方块的颜色编号（颜色不多于10种，从1开始顺序编号，相同数字表示相同颜色）。
输入数据保证初始棋盘中没有可以消除的方块。

输出描述:

如果有解决方案，输出n行，每行包含3个整数x，y，g，表示一次移动，每两个整数之间用一个空格隔开，其中（x，y）表示要移动的方块的坐标，g表示移动的方向，1表示向右移动，-1表示向左移动。注意：多组解时，按照x为第一关健字，y为第二关健字，1优先于-1，给出一组字典序最小的解。游戏界面左下角的坐标为（0，0）。
如果没有解决方案，输出一行，包含一个整数-1。

示例1

输入
3
1 0
2 1 0
2 3 4 0
3 1 0
2 4 3 4 0
输出
2 1 1
3 1 1
3 0 1
说明
按箭头方向的顺序分别为图6到图11

样例输入的游戏局面如上面第一个图片所示，依次移动的三步是：（2，1）处的方格向右移动，（3，1）处的方格向右移动，（3，0）处的方格向右移动，最后可以将棋盘上所有方块消除。
备注
对于 30%的数据，初始棋盘上的方块都在棋盘的最下面一行；
对于 100%的数据，0 < n ≤ 5。

解答

代码里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");
}


来源：Rapiz