题解 P1312 【Mayan游戏】

2018-06-24 12:47:30


其实是一道纯暴力搜索+剪枝,暴力枚举每一个点左移还是右移,并对每一次移动暴力模拟掉落和消掉的情况即可。

要注意,在搜索是应该先搜右移,因为【i,j】右移比【i+1,j】左移的字典序要小。所以在剪枝时,如果【i,j】左边不为空,就可以不走,因为之前右移已经剪过了。

还有就是移动时颜色相同可以不用搜,如果一个颜色的块数小于3且不为0,此时不可能全部消完也可以剪掉。偷懒并没有写这个剪枝,前两个已经够了,那么下面是代码

#include<cstdio>
#include<cstring> 
#include<iostream>
using namespace std;
int n;
int a[10][10];
int re[10][10];
void fall()
{
    for(int i=1;i<=5;i++)
        for(int j=1;j<=7;j++)
        {
            if(!a[i][j]) continue;
            int k=j;
            while(a[i][k-1]==0 && k>1) k--;
            swap(a[i][j],a[i][k]); 
        }
}
void print(int x)
{
    for(int i=1;i<=x;i++)
        cout<<re[i][1]-1<<" "<<re[i][2]-1<<" "<<re[i][3]<<endl;
}
bool clear()
{
    bool e[10][10];
    memset(e,0,sizeof(e));
    for(int i=1;i<=3;i++)
        for(int j=1;j<=7;j++)
            if(a[i][j]!=0 && a[i][j]==a[i+1][j] && a[i+1][j]==a[i+2][j]) e[i][j]=e[i+1][j]=e[i+2][j]=1;
    for(int i=1;i<=5;i++)
        for(int j=1;j<6;j++)
            if(a[i][j]!=0 && a[i][j]==a[i][j+1] && a[i][j+1]==a[i][j+2]) e[i][j]=e[i][j+1]=e[i][j+2]=1;
    int k=0;
    for(int i=1;i<=5;i++)
        for(int j=1;j<=7;j++)
            if(e[i][j]) a[i][j]=0,k=1;
    return k;
}
bool ok()
{
    for(int i=1;i<=5;i++)
        for(int j=1;j<=7;j++)
            if(a[i][j]) return 0;
    return 1;
}
bool dfs(int x)
{
    if(ok())
    {
        print(x-1);//注意x要-1
        return 1;
    }
    if(x>n) return 0;
    int tmp[10][10]; 
    memcpy(tmp,a,sizeof(tmp));
    for(int i=1;i<=5;i++)
        for(int j=1;j<=7;j++)
        {
            if(!a[i][j]) continue;
            if(i<5 && a[i][j]!=a[i+1][j])//剪枝1
            {
                swap(a[i][j],a[i+1][j]);
                fall();
                while(clear()) fall();//暴力循环处理掉落和消掉
                re[x][1]=i,re[x][2]=j,re[x][3]=1;
                if(dfs(x+1)) return 1;
                memcpy(a,tmp,sizeof(a));
            }
            if(i>1 && a[i-1][j]==0)//剪枝2
            {
                swap(a[i][j],a[i-1][j]);
                fall();
                while(clear()) fall();
                re[x][1]=i,re[x][2]=j,re[x][3]=-1;
                if(dfs(x+1)) return 1;
                memcpy(a,tmp,sizeof(a));
            }
        }
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=5;i++)
    {
        int x,cnt=0;
        while(++cnt)
        {
            scanf("%d",&x);
            if(x==0) break;
            a[i][cnt]=x;
        }
    }
    if(!dfs(1)) printf("-1");
    return 0;
}