luoguP1312 Mayan游戏 题解(NOIP2011)

luoguP1312 Mayan游戏 题目

#include<bits/stdc++.h>

#define ll long long

#define rg register

#define il inline

#define inf 1<<30;

using namespace std;

int a[][],b[][][];

int tmp[][];

int way[][];

int n,ans,maxn;

il ll gi()

{

    ll x=,o=;

    char ch;ch=getchar();

    while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

    if(ch=='-') o=-,ch=getchar();

    while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x*o;

}

il void input()

{

    n=gi();

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

    {

        int tmp=gi(),p=;

        while(tmp)

            a[p--][i]=tmp,tmp=gi();

        a[][i]=;

    }

}

il void print(int a[][])

{

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

    {

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

            cout<<a[i][j];

        cout<<endl;

    }

}

il void drop(int y)

{

    int p=;

    for(int i=;i>=;i--)

    {

        if(a[i][y]!=)

        {

            p=i+;

            while(a[p][y]==)

                p++;

            if(p==i+) continue;

            p-=;

            a[p][y]=a[i][y];

            a[i][y]=;

        }

    }

}

il int del(int i,int j,int deti,int detj)

{

    int fi=i,fj=j,s=;

    while()

    {

        i+=deti;j+=detj;

        if(i==||i==||j==||j==) break;

        if(tmp[i][j]!=tmp[fi][fj]) break;

        s++;

        if(s==) break;

    }

    i=fi;j=fj;

    while()

    {

        i-=deti;j-=detj;

        if(i==||i==||j==||j==) break;

        if(tmp[i][j]!=tmp[fi][fj]) break;

        s++;

        if(s==) break;

    }

    if(s>=)

    {

        a[fi][fj]=;

        return ;

    }

    return ;

}

il int delet()

{

    int flag=;

    for(int i=;i>=;i--)

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

            tmp[i][j]=a[i][j];

    for(int i=;i>=;i--)

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

        {

            if(a[i][j]==) continue;

            if(del(i,j,,)) flag=;

            if(del(i,j,,)) flag=;

        }

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

    return flag;

}

il void move(int x,int y,int mode)

{

    swap(a[x][y],a[x][y+mode]);

    drop(y);

    drop(y+mode);

    while(delet());

}

il bool check(int b[][])

{

    for(int i=;i>=;i--)

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

        {

            if(a[i][j]!=)

                return ;

        }

    return ;

}

il void reset(int k)

{

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

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

            a[l][r]=b[k][l][r];

}

il void copy(int k)

{

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

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

            b[k+][l][r]=a[l][r];

}

il void dfs(int k)

{

    if(k>n)

    {

        if(check(b[k]))

        {

            ans=;

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

            {

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

                    cout<<way[i][j]<<' ';

                cout<<endl;

            }

        }

        return;

    }

    if(ans) return;

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

    {

        for(int i=;i>=;i--)

        {

            reset(k);

            if(a[i][j]==) continue;

            if(j!=&&a[i][j+]!=a[i][j])

            {

                way[k][]=j-;

                way[k][]=-i;

                way[k][]=;

                move(i,j,);

                copy(k);

                dfs(k+);

            }

            if(ans) return;

            reset(k);

            if(j!=&&a[i][j-]==)

            {

                way[k][]=j-;

                way[k][]=-i;

                way[k][]=-;

                move(i,j,-);

                copy(k);

                dfs(k+);

            }

            if(ans)    return;

        }

    }

}

int main()

{

    input();

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

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

            b[][i][j]=a[i][j];

    dfs();

    if(!ans) cout<<"-1"<<endl;

    return ;

}