题解 P1312 【Mayan游戏】

xzy_test · 2017-10-18 14:32:24 · 题解

这道题，真的是调试了近一个月。。

一直得不了满分真的不爽。。

在龙神哈迪斯的建议下重构代码：于是A了

那么是什么意思呢，按照关键字顺序搜索：x,y,右,左

分为一下三个板块：移动，掉落，消除

加上剪枝:向左移相当于向右移，所以左移的时候要求左边是空的

那么这题按照这个步骤就可以A了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define RG register 
using namespace std;
int n;
int a[6][8];
int ans[6][4];
void in();
void DFS(int);
void print();
int main()
{
    //freopen("a.out","w",stdout);
    in();
    DFS(0);
    printf("-1\n");
    return 0;
}
inline void Diaoluo(int x)//把x这一列掉下来
{
    RG int cnt1=-1;
    for(RG int i=0;i<=6;i++)
        if(a[x][i])a[x][++cnt1]=a[x][i];
    for(RG int i=cnt1+1;i<=6;i++)a[x][i]=0;
}
inline void BOOM()//消除函数
{
    RG int flag=1;
    while(flag)
    {
        flag=0;
        RG int tmp[6][8];
        memcpy(tmp,a,sizeof(tmp));
        //Part1 判断是否可以消除
        for(RG int x=0;x<=4;x++)
        {
            for(RG int y=0;y<=6;y++)
            {
                if(x>=1&&x<=3&&tmp[x][y]&&tmp[x-1][y]==tmp[x][y]&&tmp[x+1][y]==tmp[x][y])
                {
                    a[x-1][y]=0;
                    a[x][y]=0;
                    a[x+1][y]=0;
                    flag=1;
                }
                if(y>=1&&y<=5&&tmp[x][y]&&tmp[x][y-1]==tmp[x][y]&&tmp[x][y+1]==tmp[x][y])
                {
                    a[x][y-1]=0;
                    a[x][y]=0;
                    a[x][y+1]=0;
                    flag=1;
                }
            }
        }
        if(!flag)return;
        //Part2 掉下来，回到Part1
        for(RG int i=0;i<=4;i++)Diaoluo(i);
    }
}
inline void Update_ans(int i,int x,int y,int fangxiang)
{
    ans[i][1]=x;
    ans[i][2]=y;
    ans[i][3]=fangxiang;
}
inline int pd_xiaowan()
{
    for(RG int x=0;x<=4;x++)
        for(RG int y=0;y<=6;y++)
            if(a[x][y])return 0;
    return 1;
}
void DFS(int step)//搜每一步
{
    //Part1 判断条件
    if(pd_xiaowan()&&step==n)//消除完并且步数刚好则可以
    {
        for(RG int i=1;i<=step;i++)
            printf("%d %d %d\n",ans[i][1],ans[i][2],ans[i][3]);
        exit(0);
    }
    if(step>=n)return;//超过规定步数
    //Part2 备份
    RG int tmp[6][8];
    memcpy(tmp,a,sizeof(tmp));
    //Part3 移动(关键字为x,y,先右再左)
    for(RG int x=0;x<=4;x++)
    {
        for(RG int y=0;y<=6;y++)
        {
            if(!a[x][y])continue;//空格不能移动
            if(x!=4)//没越界
            {
                swap(a[x][y],a[x+1][y]);
                Diaoluo(x);
                Diaoluo(x+1);//移动之后把这两行掉下来
                BOOM();//消除
                Update_ans(step+1,x,y,1);
                //print();
                DFS(step+1);
                //回溯
                Update_ans(step+1,0,0,0);
                memcpy(a,tmp,sizeof(a));
            }
            if(x&&!a[x-1][y])
            {
                swap(a[x][y],a[x-1][y]);
                Diaoluo(x);
                Diaoluo(x-1);
                BOOM();
                Update_ans(step+1,x,y,-1);
                //print();
                DFS(step+1);
                Update_ans(step+1,0,0,0);
                memcpy(a,tmp,sizeof(a));
            }
        }
    }
}
inline void in()
{
    cin>>n;
    for(RG int i=0;i<=4;i++)
    {
        RG int p=0;
        do{
            cin>>a[i][p];p++;
        }while(a[i][p-1]!=0);
    }
    //print();
}
void print()
{
    for(int i=0;i<=4;i++)
    {
        for(int j=0;j<=6;j++)printf("%d ",a[i][j]);
        printf("\n");
    }
    printf("\n");
}

PS：我认为右移的时候相同是可以移动的，不然若没有达到规定步数，就回输出-1 如果不加会T，只能说明你的搜索不够优秀/滑稽/