[NOI2014] 消除游戏

最近，小 Z 迷上了一款新型消除游戏。这款游戏在一个 $n\times m$ 的方格中进行。初始时方格中均为 $0 \sim 9$ 的整数。进行消除后方格中会出现空白，用 $-1$ 表示。为了方便，我们将第 $i$ 行，第 $j$ 列的数记为 $A_{i,j}$，并将其坐标记为 $(i,j)$。 给定三个参数 $l_{\min},l_{\max}$ 以及 $K$，玩家可以进行不超过 $K$ 次操作。对于每次操作，玩家需要在方格中找到一条长度为 $l$ 的路径。形式化地，该路径用两个长度为 $l$ 的序列 $x_1,x_2,\ldots,x_l$ 和 $y_1,y_2,\ldots,y_l$ 表示，需要满足如下条件： 1. $1\le x_i\le n,1\le y_i\le m$，其中 $1\le i\le l$，即 $(x_i,y_i)$ 对应于方格中的一个合法位置； 2. $\left|x_i-x_{i+1} \right|+ \left|y_i-y_{i+1} \right|=1$，其中 $1 \le i \lt l$，即 $(x_i,y_i)$ 与 $(x_{i+1},y_{i+1})$ 是方格中相邻的两个位置； 3. $x_i \neq x_j$ 或 $y_i \neq y_j$，其中 $1\le i \lt j\le l$，即路径不能经过重复的格子； 4. $A_{x_i,y_i} \neq -1$，其中 $1\le i\le l$，即路径不能经过空白的格子； 5. $A_{x_1,y_1} \neq 0$，即路径不能以数字 $0$ 为起点； 6. $l_{\min}\le l\le l_{\max}$，即路径的长度需要在给定的范围内。 将路径上的数字串成一个整数 $N$，形式化地 $$ N=\sum\limits_{i=1}^l A_{x_i,y_i}\times 10^{l-i} $$ 游戏会给出两个参数 $c_1,c_2$ 用于计算玩家本次操作的得分： 1. 如果数 $N$ 是质数，那么将获得**质数得分** $l^{c_1}$，否则获得**质数得分** $1$； 2. 如果数 $N$ 是回文数（即，将数 $N$ 的十进制表达看成一个字符串，这个字符串的逆序串和它本身完全相同），那么将获得**回文数得分** $l^{c_2}$，否则获得**回文数得分** $1$； 3. 如果**质数得分**和**回文数得分**均为 $1$，那么**本次操作的得分**为 $0$；否则**本次操作的得分**为**质数得分与回文数得分**之和。 每次操作过后，若**该次操作的得分**等于 $0$，那么你浪费了一次操作机会，而局面不会有任何改变。若**该次操作的得分**大于 $0$，则将路径上的数替换为空白，并使空白上方的数字垂直下落。形式化地，执行以下操作： 1. 执行 $A_{x_i,y_i}\leftarrow -1$，其中 $1\le i\le l$； 2. 枚举所有格子。如果存在某个格子 $(i ,j)$，满足 $i \neq n, A_{i,j} \neq -1, A_{i+1,j} = -1$，执行 $A_{i+1,j} \leftarrow A_{i,j}, A_{i,j}\leftarrow -1$。反复执行这个操作直到方格中不再存在这样的格子。 我们还会给你一个参数 $F$ ，在所有操作完成后，玩家的**最终得分** $S$ 的计算方式由 $F$ 决定：如果 $F$ 取值为 $0$，那么玩家的最终得分为所有操作的分数总和 $m$；如果 $F$ 取值为 $1$，那么玩家的最终得分为所有操作的分数总和 $m$ 除 $2^d$ 后向下取整，即 $$ S = \begin{cases} m, & F=0\\\\ \left \lfloor \frac{m}{2^d} \right \rfloor, & F=1 \end{cases} $$ 其中 $d$ 为最终方格中非空白格子的数目。 小 Z 沉迷于这个有趣的游戏中不能自拔。她想请你帮助, 针对给定的输入参数，给出游戏局面的操作方案。当然，最终得分越大越好。

**本题是一道提交答案题。** 对于每个输入文件，输入的第 $1$ 行包含 $8$ 个用空格分隔的整数 $n, m, K, l_{\min}, l_{\max}, c_1, c_2, F$，含义同题面描述。 随后 $n$ 行，每行 $m$ 个整数，表示方格 A。数之间用一个空格分隔。 输入文件中不会包含多余的空行，行末不会存在多余的空格。

针对给定的 $10$ 个输入文件 `game1.in ~ game10.in`，你需要分别提交你的输出文件 `game1.out ~ game10.out`。 输出文件第 $1$ 行为一个整数 $M (0 \leq M \leq K)$，为你的操作次数。 随后, 输出文件还应包含 $M$ 行，每行描述一次操作。对于每一行，最开始的整数$l$表示这次操作中选定路径的长度。接下来有 $2l$ 个数字，分别为 $x_1, y_1, x_2, y_2, \dots, x_l, y_l$。 输出文件中不应包含多余的空格和空行。一行的多个整数之间使用一个空格分隔。

3 3 100 2 3 1 1 0
2 1 1
2 3 3
4 7 1

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

1 3 100 2 3 1 1 1
2 1 1

1
2 1 2 1 3

#### 样例解释 1 $4$ 次消除得到的数与相应的分数分别是：$37$，得分为 $2+1=3$；$41$，得分为 $2+1=3$；$22$，得分为 $1+2=3$；$131$，得分为 $3+3=6$。总共得分为 $15$。可能存在更优的方案。 #### 样例解释 2 本方案仅一次消除操作。消除的数为 $11$，本次操作得分为 $2+2=4$。由于 $F=1$，最终得分为每次操作得分之和 $4$ 除以 $2^1 = 2$ 后下取整，为 $2$。若选择消除路径 $211$，则会得到本局面最佳分数 $4$。 #### 评分标准 对于每组数据，我们设置了 $9$ 个评分参数 $a_{10},a_9, \dots ,a_2$。如果选手的输出不合法，则得零分。否则，在你的方案中，若游戏得分为 $w_{user}$，你的分数将会由下表给出： | 得分 | 条件 | 得分 | 条件 | | :--: | :-------------------------: | :--: | :----------------------: | | $10$ | $w_{user}\ge a_{10}$ | $5$ | $a_5\le w_{user}\lt a_6$ | | $9$ | $a_9\le w_{user}\lt a_{10}$ | $4$ | $a_4\le w_{user}\lt a_5$ | | $8$ | $a_8\le w_{user}\lt a_9$ | $3$ | $a_3\le w_{user}\lt a_4$ | | $7$ | $a_7\le w_{user}\lt a_8$ | $2$ | $a_2\le w_{user}\lt a_3$ | | $6$ | $a_6\le w_{user}\lt a_7$ | $1$ | $0\lt w_{user}\lt a_2$ | #### 附加文件 checker 需要自行编译后使用。 请前往 [Github](https://github.com/MikeMirzayanov/testlib) 下载 testlib.h 的最新源代码。