luogu1312

有趣的题面

超有趣的dfs大模拟，码了巨久，卡时过了此题qaq

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,mp[][][];

struct answer{int x,y,op;}re[];

bool arr[][];

inline void fall(int now)

{

    int i,j,sz;

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

    {

        sz=;

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

        {

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

        }while(sz<) mp[now][i][sz++]=;

    }

}//顾名思义模拟方块掉落

inline void chag(int now)

{

    int i,j; bool bo=;

    for(bo=;bo;)

    {

        bo=; fall(now);

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

        {

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

            {

                if(mp[now][i][j])

                {

                    if(i<)

                    {

                        if(mp[now][i][j]==mp[now][i+][j]&&mp[now][i][j]==mp[now][i+][j])

                        {

                            bo=arr[i][j]=arr[i+][j]=arr[i+][j]=;

                        }

                    }

                    if(j<)

                    {

                        if(mp[now][i][j]==mp[now][i][j+]&&mp[now][i][j]==mp[now][i][j+])

                        {

                            bo=arr[i][j]=arr[i][j+]=arr[i][j+]=;

                        }

                    }

                }

            }

        }

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

        {

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

            {

                if(arr[i][j]) arr[i][j]=mp[now][i][j]=;

            }

        }

    }

}//找到所有连续3个的方块删去，就是这么丑qaq

inline bool dfs(int now)

{

    int i,j; for(i=;i<=;i++)for(j=;j<=;j++)mp[now][i][j]=mp[now-][i][j]; chag(now);

    if(now==n+)

    {

        for(i=;i<=;i++)if(mp[now][i][])return false; return true;

    }

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

    {

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

        {

            if(mp[now][i][j])

            {

                if(i<&&mp[now][i][j]!=mp[now][i+][j])//交换相同的毫无意义

                {

                    re[now].x=i; re[now].y=j; re[now].op=;

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

                    if(dfs(now+))return true;//暴力搜索

                    swap(mp[now][i][j],mp[now][i+][j]);//回溯

                }

                if(i&&!mp[now][i-][j])//如果上一个有的话显然是向右交换字典序更小啊

                {

                    re[now].x=i; re[now].y=j; re[now].op=-;

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

                    if(dfs(now+))return true;//搜搜搜

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

                }

            }

        }

    }return false;

}

int main()

{

    int i,j,x,bo; scanf("%d",&n); memset(arr,,sizeof arr);

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

    {

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

        {

            scanf("%d",&x); if(!x)break; mp[][i][j]=x;

        }

    }bo=dfs(); if(!bo)return *printf("-1\n");

    for(i=;i<=n;i++)printf("%d %d %d\n",re[i].x,re[i].y,re[i].op);

}