题目描述

玛雅难题是最近流行起来的一个游戏。

游戏界面是一个 7 行 5 列的棋盘，上面堆放着一些方块，方块不能悬空堆放，即方块必须放在最下面一行，或者放在其他方块之上。

游戏通关是指在规定的步数内消除所有的方块，消除方块的规则如下：

1、每步移动可以且仅可以沿横向（即向左或向右）拖动某一方块一格：当拖动这一方块时，如果拖动后到达的位置（以下称目标位置）也有方块，那么这两个方块将交换位置（参见输入输出样例说明中的图6到图7）；如果目标位置上没有方块，那么被拖动的方块将从原来的竖列中抽出，并从目标位置上掉落（直到不悬空，参见下面图1 和图2 ）；

2、任一时刻，如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块，则它们将立即被消除（参见图1 到图3）。
注意：
a) 如果同时有多组方块满足消除条件，几组方块会同时被消除（例如下面图4 ，三个颜色为1 的方块和三个颜色为 2 的方块会同时被消除，最后剩下一个颜色为 2 的方块）。
b) 当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会被同时消除（例如下面图5 所示的情形，5 个方块会同时被消除）。

3、方块消除之后，消除位置之上的方块将掉落，掉落后可能会引起新的方块消除。注意：掉落的过程中将不会有方块的消除。

上面图1 到图 3 给出了在棋盘上移动一块方块之后棋盘的变化。

棋盘的左下角方块的坐标为（0, 0），将位于（3, 3）的方块向左移动之后，游戏界面从图 1 变成图 2 所示的状态，此时在一竖列上有连续三块颜色为 4 的方块，满足消除条件，消除连续3 块颜色为4 的方块后，上方的颜色为3 的方块掉落，形成图 3 所示的局面。

输入格式
第一行为一个正整数n ，表示要求游戏通关的步数（这里指的是恰好n步通关）。

接下来的 5 行，描述 7*5 的游戏界面。

每行若干个整数，每两个整数之间用一个空格隔开，每行以一个0 结束，自下向上表示每竖列方块的颜色编号（颜色不多于10种，从1 开始顺序编号，相同数字表示相同颜色）。

输入数据保证初始棋盘中没有可以消除的方块。

输出格式
如果有解决方案，输出 n 行，每行包含 3 个整数x，y，g ，表示一次移动，每两个整数之间用一个空格隔开，其中（x ，y）表示要移动的方块的坐标，g 表示移动的方向，1 表示向右移动，-1表示向左移动。

注意：多组解时，按照 x 为第一关健字，y 为第二关健字，1优先于-1 ，给出一组字典序最小的解。

游戏界面左下角的坐标为（0 ，0）。

如果没有解决方案，输出一行，包含一个整数-1。

数据范围
对于30% 的数据，初始棋盘上的方块都在棋盘的最下面一行；
对于100%的数据，0<n≤5 。

输入样例：

3 
1 0 
2 1 0 
2 3 4 0 
3 1 0 
2 4 3 4 0

输出样例：

2 1 1 
3 1 1 
3 0 1

样例解释
按箭头方向的顺序分别为图6到图11

样例输入的游戏局面如图6所示，依次移动的三步是：

1、（2，1）处的方格向右移动。
2、（3，1）处的方格向右移动。
3、（3，0）处的方格向右移动。

最后可以将棋盘上所有方块消除。

算法1

(深度优先搜索) $O((m * n) ^ 5)$

C++ 代码(照抄Y总代码)

#include <iostream>
#include <cstring>
using namespace std;
int n; // 小方块占用地图的行数
// g[][]地图保存小方块颜色的值，bg[][][] dfs地图备份
int g[5][7], bg[5][5][7]; 
// cnt[]保存每种颜色小方块的个数，cnt[0]保存地图上小方块的总个数
// dfs时方块个数的备份
int cnt[11], bcnt[5][11]; 
bool st[5][7]; // 状态数组

struct Move { // 保存对小方块进行一次移动操作的结构体
    int x, y, d; // (x, y)小方块的坐标，d对应操作 -1向左移动 1向右移动
} path[5];

void hang() {  // 处理悬空的小方块
    for(int i = 0; i < 5; i++) {  // 枚举地图的每个位置，处理悬空的方块
        int y = 0;  // 查找从地面开始，按照纵向处理，完成后到下一列继续处理悬空小方格
        for(int j = 0; j < 7; j++) // (i, j)处有小方块悬空，依次移动到(i, y)处
            if(g[i][j]) g[i][y++] = g[i][j];  
        while(y < 7) g[i][y++] = 0; // 按纵向清理原来悬空处的小方格
    }
}

// f 告知地图更新的标记变量，false表示无需更新
// (i, j) 查找位置的起始坐标
void same(bool& f, int i, int j) { // 寻找行或列上的同色相邻的小方块
    // d, u是一行同色小方块的起始，结束的横坐标
    int d = i, u = i;  // 起止初始化为0
    // 向左查找首个同色相邻小方块的行坐标
    while(d - 1 >= 0 && g[d - 1][j] == g[i][j]) d--; 
    // 向右查找末尾同色相邻小方块的行坐标
    while(u + 1 <  5 && g[u + 1][j] == g[i][j]) u++; 
    if(u - d + 1 >= 3) { // 横向存在至少有3个方格相邻的情况
        f = true;     // 告知要更新地图
        st[i][j] = true; // 标记地图将要更新的位置(i, j)
    }
    else { // 在纵向上查看是否存在至少3个同色的方块相邻
        // d, u是一行同色小方块的起始，结束的横坐标
        d = u = j; // 起止初始化为0
        // 向下查找首个同色相邻小方块的列坐标
        while(d - 1 >= 0 && g[i][d - 1] == g[i][j]) d--; 
        // 向上查找末尾同色相邻小方块的列坐标
        while(u + 1 <  7 && g[i][u + 1] == g[i][j]) u++; 
        if(u - d + 1 >= 3) { // 纵向存在至少有3个方格相邻的情况
            f = true;     // 告知要更新地图
            st[i][j] = true; // 标记地图将要更新的位置(x, y)
        }
    }
}

void update() {  // 更新地图
    for(int i = 0; i < 5; i++)
        for(int j = 0; j < 7; j++) {
            if(!st[i][j]) continue;  // 根据更新位置标记的bool值来过滤哪些坐标不用更新
            cnt[0]--;                // 更新方块的总数
            cnt[g[i][j]]--;          // 更新每种颜色的方块的总个数
            g[i][j] = 0;             // 地图上消除当前小方块
    }
}
// (a, b)小方块原来的位置，c小方块将要或右或左移动一次的目标位置的横坐标
void clear(int a, int b, int c) {  // 消除同色相邻的小方块
    swap(g[a][b], g[c][b]); // 交换两个相邻方格的位置
    while(true) {  // 尝试消除地图上的小方块
        memset(st, false, sizeof st); // 初始化状态数组
        bool flag = false; // 表示地图是否更新，false表示不更新地图
        hang();            // 处理悬空的小方块
        for(int i = 0; i < 5; i++)
            for(int j = 0; j < 7; j++) {
                if(!g[i][j]) continue; // 地图上的当前位置(x, y)处无小方格
                // 分别在横纵方向上查看是否存在至少3个同色的方块相邻
                same(flag, i, j);
            }
        if(!flag) break;  // 无需更新地图上的小方块
        update(); // 消除同色相邻的小方块
    }
}

bool dfs(int u) {  // 查找符合规定的小方块，并且按照要求消除它们
    if(u == n) return !cnt[0];  // 已经搜索完毕，返回方块总数的非值，总数为0返回真
    for(int i = 1; i <= 10; i++) // 搜索树剪枝，同色方块的个数为1或2，显然无法消除
        if(cnt[i] == 1 || cnt[i] == 2) return false; // 该搜索分支不用搜索
    memcpy(bg[u], g, sizeof g);   // 备份地图以及每种颜色小方块的总数
    memcpy(bcnt[u], cnt, sizeof cnt);
    for(int i = 0; i < 5; i++)     // 按照字典序枚举坐标值
        for(int j = 0; j < 7; j++) {
            if(!g[i][j]) continue;  // 地图中被枚举的位置不存在小方块，进入下一轮循环
            // 第一选择，小方块向右移一格
            if(i + 1 < 5) { // 小方格向右移动一格后的位置合法
               path[u] = { i, j, 1 };  // 保存当前状态下的操作
               clear(i, j, i + 1);  // 移动方块并且消除可以消除的小方块
               if(dfs(u + 1)) return true; // 继续搜索下一状态
               memcpy(g, bg[u], sizeof g);  // 恢复之前的状态，便于回溯
               memcpy(cnt, bcnt[u], sizeof cnt);
            }
            // 第二选择，小方块向左移一格
            if(i - 1 >= 0 && !g[i - 1][j]) { // 位置合法且该位置为空
               path[u] = { i, j, -1 };
               clear(i, j, i - 1);
               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 j = 0, c; // 纵坐标，颜色值
        while(cin >> c, c) { // 颜色值为0，表示一行的输入结束
            cnt[0]++;  // 小方块的总数加一
            cnt[c]++;  // 对应颜色的小方块总数加一
            g[i][j++] = c; // 在地图的同一列上依次放置小方块 
        }
    }

    if(!dfs(0)) puts("-1"); // 无解
    else for(int i = 0; i < n; i++) // 输出消除小方块的所有方案
             cout << path[i].x << " " << path[i].y << " " << path[i].d << endl;

    return 0;
}