题解|《算法竞赛进阶指南》 Mayan 游戏

题意

Mayan puzzle是一个游戏。界面是一个 7 行5 列的棋盘，上面堆放着一些方块，方块不能悬空堆放。

具体规则：

 1. 每步移动可以且仅可以沿横向拖动某一方块一格：当拖动这一方块时，如果拖动后到达的位置；
    如果目标位置上没有方块，那么被拖动的方块将从原来的竖列中抽出，并从目标位置上掉落；
 2.任一时刻，如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块，则它们将立即被消除

 注意：
 a) 如果同时有多组方块满足消除条件，几组方块会同时被消除。
 b) 当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会被同时消除。
 c) 方块消除之后，消除位置之上的方块将掉落，掉落后可能会引起新的方块消除。注意：掉落的过程中将不会有方块的消除。

题解

暴力dfs（注意从左下角开始，并且按照字典序（这样搜到的第一种就是字典序最小的））并不断对每个方块进行向左和向右两种操作（先向右）

剪枝：
 1.交换两个颜色相同的块没有意义
 2.一个块的左边是非空块时不需要考虑左移,（会和之前的块右移重复）即只有当左块为空时才左移
 3.如果有一种颜色当前的块数目x满足1<=x<=2，则不肯能消完，退出
 4.dfs时先考虑右移(这样搜到的第一种就是字典序最小的)

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
int n,map[9][7],x[1000],y[1000],way[1000],p=0;
bool if_can=false; //判断是否可以 
void outputmap(){
    cout<<"-----------------"<<endl;
    for (int i=7;i>=1;i--){
        for (int j=1;j<=5;j++)
            cout<<map[i][j]<<' ';
        cout<<endl;
    }
    cout<<"-----------------"<<endl; 
}
int else_num(){
    int sum=0;
    for (int i=1;i<=7;i++)
        for (int j=1;j<=5;j++)
            if (map[i][j]) sum++;
    return sum;
}//剩余方块个数
int del(){
    bool pd=true;
    int k,j,i;
    int map2[8][6];
    for (i=1;i<=7;i++)
        for (j=1;j<=5;j++)
            map2[i][j]=map[i][j];

    for (i=1;i<=7;i++){
        for (j=1;j<=3;j++)
            if (map[i][j]!=0&&map[i][j]==map[i][j+1]&&map[i][j+1]==map[i][j+2]){
                for (k=j;map[i][k]==map[i][j];k++){
                    map2[i][k]=0;
                    pd=false;
                }
            j=k+1;
            }      
    }
    for (j=1;j<=5;j++){
        for (i=1;i<=5;i++)
            if (map[i][j]!=0&&map[i][j]==map[i+1][j]&&map[i+1][j]==map[i+2][j]){
                for (k=i;map[k][j]==map[i][j];k++){
                    map2[k][j]=0;
                    pd=false;
                }
            i=k+1;
            }      
    }
    for (i=1;i<=7;i++)
        for (j=1;j<=5;j++)
            map[i][j]=map2[i][j];
    if (pd) return 0;
    else return 1;
}
void drop1(){
    for (int j=1;j<=5;j++){
        for (int i=7;i>=1;i--){
            if (map[i][j]==0){
                for (int k=i;k<7;k++)
                map[k][j]=map[k+1][j];
            }
        }
    }
}
void drop(){
    int len[6];
    memset(len,0,sizeof(len));
    for (int j=1;j<=5;j++){
        for (int i=7;i>=1;i--)
            if (map[i][j]) {
                len[j]=i;
                break;
            }    

        for (int i=len[j];i>=1;i--){
            if (!map[i][j]) {
                for (int ij=i;ij<=7;ij++)
                    map[ij][j]=map[ij+1][j];
            }
        }
    }
}
void swap(int &a,int &b){
    int t;
    t=a;a=b;b=t;
}
int able(){
    int pd[11];
    memset(pd,0,sizeof(pd));
    for (int i=1;i<=7;i++)
        for (int j=1;j<=5;j++)
        pd[map[i][j]]++;
    for (int i=1;i<=10;i++)
        if (pd[i]>=1&&pd[i]<=2) return 1;
    return 0;
}
void dfs(int num){
    drop();
    while (del()){  //消去可以消的
            drop();  //悬空块掉落
    }
    if (able()) return;
    if (num==n+1){
        if (else_num()==0) {
            //outputmap();
            for (int i=1;i<=n;i++)
            cout<<y[i]-1<<' '<<x[i]-1<<' '<<way[i]<<endl;
            exit(0);
            if_can=true;
        }
        return; 
    }
    int map_back[8][6];
    for (int i=1;i<=7;i++)    for (int j=1;j<=5;j++)    map_back[i][j]=map[i][j];

    for (int j=1;j<=5;j++)
    for (int i=1;i<=7;i++)   {    
        if (map[i][j]){

        if (map[i][j]!=map[i][j+1]&&j<5) {
x[num]=i;y[num]=j;way[num]=1;
            swap(map[i][j+1],map[i][j]);
            dfs(num+1);
           }     

        for (int i=1;i<=7;i++)     for (int j=1;j<=5;j++)    map[i][j]=map_back[i][j];

        if (map[i][j-1]==0&&j>1) {
x[num]=i;y[num]=j;way[num]=-1;
            swap(map[i][j-1],map[i][j]);
            dfs(num+1);

           }
         for (int i=1;i<=7;i++)     for (int j=1;j<=5;j++)    map[i][j]=map_back[i][j];      
        }
    }

}
int main(){
    memset(map,0,sizeof(map));
    cin>>n;
    for(int i=1;i<=5;i++){
        int j=0,t;
        cin>>t;
        while(t!=0){
            j++;
            map[j][i]=t;
            cin>>t; 
        }
    }
    //outputmap();
    dfs(1);
    if (!if_can) cout<<-1<<endl; 
    return 0;
}