题解 P1312 【Mayan游戏】

Whyher · 2019-09-07 22:21:28 · 题解

蒟蒻花了几个小时才调出来，其实只要一道暴力搜索，基本不用剪枝。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int get[10][10];\\初始的棋盘；
int m;
struct node
{
    int x,y,z;\\用结构体记录答案；
};
node ans[10];
int tot[10][10];
int finish;\\进行判断，是否找到解，避免超时；
void print()\\输出函数；
{
    for(int i=1;i<=m;i++)
        printf("%d %d %d\n",ans[i].x-1,ans[i].y-1,ans[i].z);
}
void dfs(int p[10][10],int num)
{
    if(finish==1)return;
    if(num>m)
    {
        int f=0;
        for(int i=1;i<=5;i++)
            for(int j=1;j<=7;j++)
                if(p[i][j])\\当到达次数时遍历棋盘是否为空；
                    f=1;
        if(f==0)\\为空输出；
        {
            print();
            finish=1;
        }
        return; 
    }
    for(int k=1;k<=4;k++)\\可以吧空的点当做0，每个点只向右移；
    {
        for(int l=1;l<=7;l++)
        {
            if(p[k][l]!=p[k+1][l])\\一点点剪枝；
            {
                int tmp[10][10];
                for(int i=1;i<=5;i++)
                    for(int j=1;j<=7;j++)
                        tmp[i][j]=p[i][j];
                swap(tmp[k][l],tmp[k+1][l]);\\移动；
                int flag=1;

                while(flag==1)\\当能消除时一直消除；
                {
                    flag=0;
                    int news[10][10];
                    int h[6];
                    memset(news,0,sizeof(news));
                    memset(h,0,sizeof(h));
                    for(int i=1;i<=5;i++)\\下沉；
                        for(int j=1;j<=7;j++)
                            if(tmp[i][j]!=0)
                                news[i][++h[i]]=tmp[i][j];
                    int tot[10][10];
                    memset(tot,0,sizeof(tot));
                    for(int i=1;i<=5;i++)\\判断可不可以删除，删除几个；
                    {
                        for(int j=1;j<=7;j++)
                        {
                            if(news[i][j]==0)continue;
                            int sum1=1,sum2=1;
                            for(int o=1;o<=5;o++)
                            {
                                if(i+o<=5&&news[i+o][j]==news[i][j])
                                    sum1++;
                                else break;
                                }   
                            if(sum1>=3)
                                for(int o=i;o<=i+sum1-1;o++)
                                    tot[o][j]=-1;
                            for(int o=1;o<=7;o++)
                                {
                                    if(j+o<=7&&news[i][j+o]==news[i][j])
                                    sum2++;
                                else break;

                                }
                            if(sum2>=3)
                            for(int o=j;o<=j+sum2-1;o++)
                                tot[i][o]=-1;
                            if(sum2>=3||sum1>=3)flag=1;                         
                        }
                    }   
                    for(int i=1;i<=5;i++)
                        for(int j=1;j<=7;j++)
                            if(tot[i][j]==-1)
                                news[i][j]=0;
                    for(int i=1;i<=5;i++)
                        for(int j=1;j<=7;j++)
                            tmp[i][j]=news[i][j];
                }
                if(p[k][l]!=0)\\因为刚刚假设0可以移动，但实际零不能移动，特判一下移动零的情况；
                {
                    ans[num].x=k;
                    ans[num].y=l;
                    ans[num].z=1;
                }
                else 
                {
                    ans[num].x=k+1;
                    ans[num].y=l;
                    ans[num].z=-1;
                }
                dfs(tmp,num+1);
            }
        }
    }
}
int main()
{
    scanf("%d",&m);
    for(int i=1;i<=5;i++)
    {
        int x;
        for(int j=1;j<=8;j++)
        {
            scanf("%d",&x);
            if(x==0)break;
            get[i][j]=x;
        }
    }
    dfs(get,1);
    if(finish==0)\\未找到输出-1；
        cout<<-1<<endl;
    return 0;\\over;
}

第二篇题解望通过，谢谢大佬；