玛雅难题

题目描述

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

游戏界面是一个 7 行 5 列 的棋盘，上面堆放着一些方块。

游戏规则

1. 方块堆放规则

• 方块不能悬空堆放
• 方块必须放在最下面一行，或者放在其他方块之上

2. 移动规则（每步只能进行一次移动）

每步移动可以且仅可以沿横向（向左或向右）拖动某一方块一格：

情况A： 如果拖动后到达的目标位置也有方块，那么这两个方块将交换位置（参见输入输出样例说明中的图6到图7）

情况B： 如果目标位置上没有方块，那么被拖动的方块将从原来的竖列中抽出，并从目标位置上掉落（直到不悬空，参见图1和图2）

3. 消除规则

任一时刻，如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块，则它们将立即被消除。

注意： a) 如果同时有多组方块满足消除条件，几组方块会同时被消除（例如图4，三个颜色为1的方块和三个颜色为2的方块会同时被消除） b) 当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会同时被消除（例如图5所示的情形）

4. 掉落与连锁消除

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

坐标系统

• 棋盘的左下角方块的坐标为 (0,0)
• x轴：从左到右（0-4）
• y轴：从下到上（0-6）

输入格式

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

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

每行若干个整数，每两个整数之间用一个空格隔开，每行以一个 0 结束，自下向上表示每竖列方块的颜色编号：

• 颜色不多于 10 种，从 1 开始顺序编号
• 相同数字表示相同颜色
• 输入数据保证初始棋盘中没有可以消除的方块

输出格式

如果有解决方案： 输出 n 行，每行包含 3 个整数 x, y, g，表示一次移动：

• (x, y) 表示要移动的方块的坐标
• g 表示移动的方向：1 表示向右移动，-1 表示向左移动
• 每两个整数之间用一个空格隔开

注意： 多组解时，按照以下优先级给出字典序最小的解：

1. x 为第一关键字（从小到大）
2. y 为第二关键字（从小到大）
3. 1 优先于 -1（向右移动优先于向左移动）

如果没有解决方案： 输出一行，包含一个整数 -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所示：

初始棋盘（自下向上，每列单独看）：

• 第0列：1 （只有1个方块，颜色1，y=0位置）
• 第1列：2, 1 （2个方块，底部颜色2 y=0，上面颜色1 y=1）
• 第2列：2, 3, 4 （3个方块，底部颜色2 y=0，中间颜色3 y=1，顶部颜色4 y=2）
• 第3列：3, 1 （2个方块，底部颜色3 y=0，上面颜色1 y=1）
• 第4列：2, 4, 3, 4 （4个方块，底部颜色2 y=0，然后颜色4 y=1，颜色3 y=2，颜色4 y=3）

依次移动的三步是：

1. (2, 1) 处的方格向右移动
2. (3, 1) 处的方格向右移动
3. (3, 0) 处的方格向右移动

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

按箭头方向的顺序分别为图6到图11。

游戏示例

题目中图示说明：

• 图1到图3：展示了移动方块后的消除过程
  • 将位于(3,3)的方块向左移动
  • 形成一竖列上有连续三块颜色为4的方块
  • 消除后上方的颜色为3的方块掉落
• 图4：同时消除多组方块的示例
• 图5：行列共享方块的消除示例
• 图6到图11：样例的完整解决过程

时空限制

• 时间限制：1秒
• 空间限制：64MB