3680. 魔板

单点时限: 3.0 sec

内存限制: 256 MB

“闭上眼睛,好好回想之前的努力,自信会喷涌而出。”

QQ 小方闭上眼睛,开始熟练地还原魔方。

一直是这样的挑战,显得索然无味。于是 QQ 小方发明了一种新的谜题:魔板。

魔板是一个由 $n\times m$ 个三角形组成的平行四边形,魔板有 $n$ 行 $m$ 列个端点。行从下至上标记为 $1$ 到 $n$,列从左到右标记为 $1$ 到 $m$。每个端点都由坐标 $(x,y)$ 表示,其中 $x$ 是行,$y$ 是列。每个端点都用一个 $1$ 到 $n\cdot m$ 之间的唯一整数值表示,代表这个端点的初始标号。

  • 第一行的端点从左到右依次标号为 $1,2,3,\ldots,m$。
  • 第二行的端点依次标号为 $m+1,m+2,\ldots,2m$。
  • ……

如下图是一个 $3\times 4$ 魔板的初始标号:

魔板有以下两种变换方式:

  • 选择一个三角形(设三角形的左下角端点坐标为 $(x,y)$ ,则上面端点的坐标为 $(x+1,y)$ ,右下角端点坐标为 $(x,y+1)$),做一次顺时针旋转(左下角到上面,上面到右下角,右下角到左下角)。
  • 选择一个菱形(设菱形的左下角端点坐标为 $(x,y)$ ,则左上角端点的坐标为 $(x+1,y)$ ,右下角端点坐标为 $(x,y+1)$ ,右上角坐标为 $(x+1,y+1)$),做一次顺时针旋转(左下角到左上角,以此类推)。

QQ 小方又闭上眼睛了,你能打败他吗?

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2\le n,m\le 100$)。

接下来 $n$ 行,每行 $m$ 个数,表示打乱以后的魔板。

输出格式

第一行输出一个整数 $T$ ,表示操作的次数。

接下来的 $T$ 行,每行三个整数 $opt,x,y$ ,表示执行的操作。

  • $opt=1$ 表示执行三角形顺时针旋转操作,其中左下角的坐标为 $(x,y)$。
  • $opt=2$ 表示执行菱形顺时针旋转操作,其中左下角的坐标为 $(x,y)$。

在执行 $T$ 次操作后,魔板回到了初始状态,且不存在非法操作,而且满足 $T\le 3\cdot 10^6$,则认为是正确的。

样例

Input
2 3
4 1 2
5 6 3
Output
2
1 1 1
2 1 2
Input
2 3
1 2 3
4 5 6
Output
0

提示

对于第一个样例的解释:

打乱以后魔板的状态:

5 6 3
4 1 2

执行操作 1 1 1 以后魔板的状态:

4 6 3
1 5 2

执行操作 2 1 2 以后魔板的状态:

4 5 6
1 2 3

魔板回到了初始状态。

2 人解决,5 人已尝试。

2 份提交通过,共有 26 份提交。

9.4 EMB 奖励。

创建: 1 年,4 月前.

修改: 1 年,4 月前.

最后提交: 1 年,3 月前.

来源: EOJ Monthly 2019.2

题目标签