#include<bits/stdc++.h>
using namespace std;
int n;
int g[5][7], bg[5][5][7];
int cnt[11], bcnt[5][11];
bool st[5][7];

struct Path{
    int x, y, d;
}path[5];

void move(int a, int b, int c)
{
    swap(g[a][b], g[c][b]);

    while(true)
    {
        bool flag = true;

        //处理悬空方格
        for(int x = 0; x < 5; x ++)
        {
            int z = 0;
            for(int y = 0; y < 7; y++)
                if(g[x][y])
                    g[x][z ++] = g[x][y];
            while(z < 7) g[x][z ++] = 0;
        }

        memset(st, 0, sizeof st);
        for(int x = 0; x < 5; x++)
            for(int y = 0; y < 7; y ++)
            {
                if(g[x][y])
                {
                    int l = x, r = x;
                    while(l - 1 >= 0 && g[l - 1][y] == g[x][y]) l--;
                    while(r + 1 < 5 && g[r + 1][y] == g[x][y]) r ++;
                    if(r - l + 1 >= 3)
                    {
                        st[x][y] = true;
                        flag = false;
                    }
                    else
                    {
                        l = r = y;
                        while(l - 1 >= 0 && g[x][l-1] == g[x][y]) l--;
                        while(r + 1 < 7 && g[x][r+1] == g[x][y]) r ++;
                        if(r - l + 1 >= 3)
                        {
                            st[x][y] = true;
                            flag = false;
                        }
                    }
                }
            }
        if(flag) break;
        for(int x = 0; x < 5; x++)
            for(int y = 0; y < 7; y++)
                if(st[x][y])
                {
                    cnt[0] --;
                    cnt[g[x][y]] --;
                    g[x][y] = 0;
                }
    }

    
}

bool dfs(int u)
{
    if(u == n) return cnt[0] == 0;

    for(int i = 1; i <= 10; i++)
        if(cnt[i] == 1 || cnt[i] == 2)
            return false;
    
    //枚举所有的操作
    memcpy(bg[u], g, sizeof g);
    memcpy(bcnt[u], cnt, sizeof cnt);

    for(int x = 0; x < 5; x ++)
        for(int y = 0; y < 7; y++)
        {
            if(g[x][y])
            {
                int nx = x + 1;
                if(nx < 5)
                {
                    path[u] = {x, y, 1};
                    move(x, y, nx);
                    if(dfs(u + 1)) return true;
                    //恢复现场
                    memcpy(g, bg[u], sizeof g);
                    memcpy(cnt, bcnt[u], sizeof cnt);
                }

                nx = x - 1;
                if(nx >= 0 && g[nx][y] == 0)
                {
                    path[u] = {x, y, -1};
                    move(x, y, nx);
                    if(dfs(u + 1)) return true;
                    memcpy(g, bg[u], sizeof g);
                    memcpy(cnt, bcnt[u], sizeof cnt);
                }
            }
        }
    return false;
}

int main()
{
    cin >> n;
    for(int i = 0; i < 5; i++)
    {
        int t, j = 0;
        while(cin >> t && t)
        {
            cnt[0] ++; //现在方块的个数
            cnt[t] ++;
            g[i][j ++] = t;
        }
    }
    if(dfs(0))
    {
        for(int i = 0; i < n; i++)
            cout << path[i].x << " " << path[i].y << " " << path[i].d << endl;
    }
    else 
        cout << -1 << endl;
    return 0;
}

/*
暴搜

搜索顺序:依次枚举每一步选择哪个方块,以及枚举向左移动还是向右移动

剪枝:
1.把向左移动时如果左侧有方块,则直接剪掉。
2.当某种颜色的方块数量大于0且小于3时,一定无解。

模拟消除:
1.处理悬空
2.处理消除
*/

0 条评论

目前还没有评论...