洛谷 P1312 [ NOIP 2011 ] Mayan游戏 —— 搜索+模拟

题目：https://www.luogu.org/problemnew/show/P1312

还是不擅长这种题，所以参考了一下TJ；

其实也很好搜，按字典序，先搜右移，再搜左移；

不交换相同颜色的两个格子，因为浪费；

左移就不交换了，避免重复，只有左边为空时左移；

写个处理下落的 fall 函数，再写个处理消格子的 refresh 函数(其中用到了 fall )，就可以方便地搜索了！

我存的是行和列，所以和坐标正好相反，一定要注意字典序的处理！

优美。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,mp[][][],ansx[],ansy[],ansm[];

bool vis[][];

void fall(int s)

{

    for(int j=,sz;j<=;j++)

    {

        sz=;

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

            if(mp[s][i][j])mp[s][++sz][j]=mp[s][i][j];

        while(sz<)mp[s][++sz][j]=;//

    }

}

void refresh(int s)

{

    bool fl=;

    while()

    {

        fl=; fall(s);

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

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

            {

                if(!mp[s][i][j])continue;//

                if(i<=&&mp[s][i][j]==mp[s][i+][j]&&mp[s][i][j]==mp[s][i+][j])

                {

                    fl=;

                    vis[i][j]=vis[i+][j]=vis[i+][j]=;

                }

                if(j<=&&mp[s][i][j]==mp[s][i][j+]&&mp[s][i][j]==mp[s][i][j+])

                {

                    fl=;

                    vis[i][j]=vis[i][j+]=vis[i][j+]=;

                }

            }

        if(!fl)break;

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

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

                if(vis[i][j])mp[s][i][j]=,vis[i][j]=;

    }

}

bool dfs(int s)

{

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

        for(int j=;j<=;j++)mp[s][i][j]=mp[s-][i][j];

    refresh(s);

    if(s>n)

    {

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

            if(mp[s][][j])return ;

        return ;

    }

    for(int j=;j<=;j++)//字典序！

        for(int i=;i<=;i++)    if(mp[s][i][j])

        {

            if(j<&&mp[s][i][j]!=mp[s][i][j+])//

            {

                ansx[s]=i; ansy[s]=j; ansm[s]=;

                swap(mp[s][i][j],mp[s][i][j+]);

                if(dfs(s+))return ;

                swap(mp[s][i][j],mp[s][i][j+]);

            }

            if(j>&&!mp[s][i][j-])//-1

            {

                ansx[s]=i; ansy[s]=j; ansm[s]=-;

                swap(mp[s][i][j],mp[s][i][j-]);

                if(dfs(s+))return ;

                swap(mp[s][i][j],mp[s][i][j-]);

            }

        }

    return ;

}

int main()

{

    scanf("%d",&n);

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

        for(int i=,x;i<=;i++)

        {

            scanf("%d",&x); if(!x)break;

            mp[][i][j]=x;

        }

    if(dfs())//

    {

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

            printf("%d %d %d\n",ansy[i]-,ansx[i]-,ansm[i]);//坐标！

    }

    else printf("-1\n");

    return ;

}