【Luogu】P1312Mayan游戏（暴搜）

　　由于是暴搜题，所以这篇博客只讲怎么优化剪枝，以及一些细节。

　　模拟消除思路：因为消除可以拆分成小的横条或竖条，而这些条的长度至少为三，所以一块可消除的区域至少会有一个中心点。这里的中心点可以不在正中间，只需要不是条上的第一个或者最后一个。

　　于是枚举中间点，搜索它为中心最多向四个方向能扩展多远。如果搜索出来的横向满足长度要求，或竖向满足长度要求，就给他们打上一个标记。

　　注意，这里只是打上标记，不能直接清零，很可能另一个方块的结算还得用到这个方块。

　　等到枚举所有的中间点并给所有可消除的方块打上标记之后，可以把所有标记上的方块清空。然后检查有没有地方可以落下去。

　　注意所有方块落下去之后还有可能接着消消乐，所以在落完之后还要再循环回去检查有没有可消除的方块。这里使用一个递归的代码来实现。

int count(int x){

    bool vis[][],flag=;

    int cnt=;

    memset(vis,,sizeof(vis));

    for(register int i=;i<=n;++i)

        for(register int j=;j<=m;++j){

            int col=Map[x][i][j];

            if(!col)    continue;

            int u=i,d=i,l=j,r=j;

            while(u>&&Map[x][u-][j]==col)    u--;

            while(d<n&&Map[x][d+][j]==col)    d++;

            while(l>&&Map[x][i][l-]==col)    l--;

            while(r<m&&Map[x][i][r+]==col)    r++;

            if(d-u>=)

                for(int k=u;k<=d;++k)    vis[k][j]=;

            if(r-l>=)

                for(int k=l;k<=r;++k)    vis[i][k]=;

        }

    for(register int i=;i<=n;++i)

        for(register int j=;j<=m;++j)

            if(vis[i][j]){

                Map[x][i][j]=;    cnt++;

            }

    for(register int i=;i<=n;++i)

        for(register int j=;j<=m;++j)

            if(!Map[x][i][j]){

                int s=i;

                while(s<n&&!Map[x][s][j])    s++;

                if(!Map[x][s][j])    continue;

                flag=;

                Map[x][i][j]=Map[x][s][j];

                Map[x][s][j]=;

            }

    if(flag)    cnt+=count(x);

    return cnt;

}

注意最后倒数第三行。flag表示的是有没有方块落下，因为有落下方块就有新一轮消除的可能性，所以可以递归这个函数，直到没有任何方块落下为止。此时递归终止，开始回溯计算答案。　　

　　再说说剪枝的几个小技巧。

　　1、优先考虑坐标字典序小的向右移动，这样一旦搜到答案就是字典序最小的解。

　　2、只有当左边没有方块的时候才向左移动，否则右面方块向左移动等价于左面方块向右移动，而这个状态已经搜过了。

　　3、不交换两个颜色相同的方块。这个没什么好说的。

　　最后给出代码。

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cctype>

#include<cstring>

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

int num;

int n=,m=;

int Max;

int Map[][][];

int posx[],posy[],move[];

inline void copy(int x){

    for(register int i=;i<=n;++i)

        for(register int j=;j<=m;++j)    Map[x+][i][j]=Map[x][i][j];

}

int count(int x){

    bool vis[][],flag=;

    int cnt=;

    memset(vis,,sizeof(vis));

    for(register int i=;i<=n;++i)

        for(register int j=;j<=m;++j){

            int col=Map[x][i][j];

            if(!col)    continue;

            int u=i,d=i,l=j,r=j;

            while(u>&&Map[x][u-][j]==col)    u--;

            while(d<n&&Map[x][d+][j]==col)    d++;

            while(l>&&Map[x][i][l-]==col)    l--;

            while(r<m&&Map[x][i][r+]==col)    r++;

            if(d-u>=)

                for(int k=u;k<=d;++k)    vis[k][j]=;

            if(r-l>=)

                for(int k=l;k<=r;++k)    vis[i][k]=;

        }

    for(register int i=;i<=n;++i)

        for(register int j=;j<=m;++j)

            if(vis[i][j]){

                Map[x][i][j]=;    cnt++;

            }

    for(register int i=;i<=n;++i)

        for(register int j=;j<=m;++j)

            if(!Map[x][i][j]){

                int s=i;

                while(s<n&&!Map[x][s][j])    s++;

                if(!Map[x][s][j])    continue;

                flag=;

                Map[x][i][j]=Map[x][s][j];

                Map[x][s][j]=;

            }

    if(flag)    cnt+=count(x);

    return cnt;

}

void dfs(int use,int deep){

    if(use!=&&deep==Max)    return;

    if(use==){

        if(deep==Max){

            for(int i=;i<=Max;++i)    printf("%d %d %d\n",posy[i]-,posx[i]-,move[i]);

            exit();

        }

        return;

    }

    copy(deep);

    for(register int j=;j<=m;++j)

        for(register int i=;i<=n;++i){

            if(!Map[deep][i][j])    continue;

            if(Map[deep][i][j]!=Map[deep][i][j+]&&j<m){

                int a=Map[deep][i][j],b=Map[deep][i][j+];

                Map[deep+][i][j]=b;Map[deep+][i][j+]=a;

                posx[deep+]=i;    posy[deep+]=j;    move[deep+]=;

                int q=count(deep+);

                dfs(use-q,deep+);

                copy(deep);

            }

            if(!Map[deep][i][j-]&&j>){

                int a=Map[deep][i][j],b=Map[deep][i][j-];

                Map[deep+][i][j]=b;Map[deep+][i][j-]=a;

                posx[deep+]=i;    posy[deep+]=j;    move[deep+]=-;

                int s=i;

                while(s>&&Map[deep+][s-][j-]==){

                    Map[deep+][s--][j-]=;

                    Map[deep+][s][j-]=a;

                }

                int q=count(deep+);

                dfs(use-q,deep+);

                copy(deep);

            }

        }

}

int main(){

    Max=read();

    int start=;

    for(int i=;i<=m;++i)

        for(int j=;;j++){

            Map[][j][i]=read();

            if(Map[][j][i]==)    break;

            start++;

        }

    dfs(start,);

    printf("-1");

    return ;

}

巴特西

【Luogu】P1312Mayan游戏（暴搜）

最新文章

热门文章