题解 P1312 【Mayan游戏】

yeyyx · 2017-10-26 16:44:30 · 题解

大搜索终于ac了！写+调试了3，4个小时

主要卡在了：字典序最小其实就是你搜索到的第一组数据（注意下搜索顺序就行：0~5/7，先右后左）

所以搜到一组解输出 退出就行。

和月赛一道大水题一样，有效练习代码能力otz

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#define z 10
using namespace std;
int m[z][z],ms[z][z][z],cl[z][z],ans[z][z],fin[z][z];
int n,ti;
void fall(){
    for(int i=0;i<5;i++){
        int zero=0;
        for(int j=0;j<7;j++){
            if(m[i][j]==0)++zero;
            else{
                if(zero==0)continue; 
                m[i][j-zero]=m[i][j];
                m[i][j]=0;
            }
        }
    }

}//向下降落_填充

bool clear(){
    int cnt=0;
    memset(cl,0,sizeof cl);
    for(int i=0;i<5;i++)
        for(int j=0;j<7;j++){
            if(i-1>=0&&i+1<5&&m[i][j]&&m[i][j]==m[i-1][j]&&m[i][j]==m[i+1][j]){
                cl[i][j]=1;cl[i+1][j]=1;cl[i-1][j]=1;cnt=1;
            }
            if(j-1>=0&&j+1<7&&m[i][j]&&m[i][j]==m[i][j-1]&&m[i][j]==m[i][j+1]){
                cl[i][j]=1;cl[i][j+1]=1;cl[i][j-1]=1;cnt=1;
            }
        }
    if(!cnt)return 0;
    for(int i=0;i<5;i++)
        for(int j=0;j<7;j++){
            if(cl[i][j]){
                m[i][j]=0;
            }
        }
    return 1;
}
void save(int d){
    for(int i=0;i<5;i++)
        for(int j=0;j<7;j++)
            ms[d][i][j]=m[i][j];
}
void re(int d){
    for(int i=0;i<5;i++)
        for(int j=0;j<7;j++)
            m[i][j]=ms[d][i][j];
    for(int i=0;i<3;i++)ans[d][i]=-1;
}
bool check(){
    for(int i=0;i<5;i++)
        for(int j=0;j<7;j++)
            if(m[i][j]!=0)return 0;
    return 1;
}
void move(int i,int j,int p){
        int t=m[i][j];
        m[i][j]=m[i+p][j];
        m[i+p][j]=t;
    fall();
    while(clear()){
        fall();
    }
}
void dfs(int d){
    if(check()){
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                printf("%d ",ans[i][j]);
            }
            printf("\n");
        }
        exit(0);
    }
    if(d==n)return;
    save(d);
    for(int i=0;i<5;i++){
        for(int j=0;j<7;j++){
            if(m[i][j]){
                if(i<4&&m[i+1][j]!=m[i][j]){
                    move(i,j,1);ans[d][0]=i;
                    ans[d][1]=j;ans[d][2]=1;
                    dfs(d+1);re(d);
                }
                if(i>0&&m[i-1][j]==0){
                    move(i,j,-1);ans[d][0]=i;
                    ans[d][1]=j;ans[d][2]=-1;
                    dfs(d+1);re(d);
                }
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<5;i++){
        for(int j=0;j<=7;j++){
            int tt;
            scanf("%d",&tt);
            if(tt==0)break;
            m[i][j]=tt;
        }
    }
    memset(fin,-1,sizeof fin);
    dfs(0);
    if(fin[1][0]==-1)printf("-1\n");
    return 0;
}