P17900 [ICPC 2026 Nanchang I] Kingdam of Construction

题目描述

你正在管理构造王坝(Kingdam of Construction)的阀门矩阵。 给定一个 $n\times m$($n$ 和 $m$ 均为偶数)的矩阵 $a$,$a$ 里的元素均为 $1$ 到 $n\times m$ 之间的正整数且两两不同。 你可以进行以下两种操作(任意顺序): - 选择第 $i$ ($1\le i\le n$) 行,将其左右翻转,即对于所有 $1\le j\le \frac m2$,交换 $a_{i,j}$ 与 $a_{i,m-j+1}$; - 选择第 $j$ ($1\le j\le m$) 列,将其上下翻转,即对于所有 $1\le i\le \frac n2$,交换 $a_{i,j}$ 与 $a_{n-i+1,j}$。 求能否经过有限次操作把 $a$ 变为 $n\times m$ 的目标矩阵 $b$,其中 $b$ 按行优先顺序依次填入 $1,2,\ldots,n\times m$,即 $b_{i,j}=(i-1)\times m+j$。如果可以,请构造一个**操作次数不超过 $9961$ 的**操作序列(也可以不进行任何操作,即操作序列为空)。可以证明,如果存在一个操作序列,则必存在一个操作次数不超过 $9961$ 的操作序列。

输入格式

有多组测试数据。输入的第一行包含一个正整数 $t$ ($1\le t\le 25$),表示测试数据的组数。对于每组测试数据: 第一行包含两个正整数 $n$ 和 $m$ ($2\le n\le 134$, $2\le m\le 134$),分别表示矩阵 $a$ 的行数与列数。 接下来 $n$ 行,每行包含 $m$ 个正整数 $a_{i,1},a_{i,2},\ldots,a_{i,m}$,表示矩阵 $a$ 的元素。 保证 $n$ 和 $m$ 均为偶数;保证 $1$ 到 $n\times m$ 之间的每个正整数在矩阵 $a$ 中恰好出现一次。

输出格式

对于每组测试数据: 如果可以在有限次操作内将矩阵 $a$ 变为目标矩阵 $b$,在第一行中打印 “`Yes`”。 接下来一行包含一个非负整数 $cnt$,表示你的操作次数。你需要保证 $0\le cnt\le 9961$(对于每组测试数据,即对所有测试数据的 $cnt$ 之和没有限制)。 接下来 $cnt$ 行,每行包含两个整数 $op$ 和 $idx$($op\in\{0,1\}$,若 $op=0$ 则 $1\le idx\le n$,否则 $1\le idx\le m$),$op=0$ 表示将第 $idx$ 行翻转,$op=1$ 表示将第 $idx$ 列翻转。 如果不存在合法的操作方案,仅输出一行包含 “`No`”。 你可以输出任意大小写形式的答案。例如,字符串 “`yEs`”、“`yes`”、“`Yes`”、“`YES`” 均会被接受为肯定回答。

说明/提示

对于样例的第二组数据,操作过程如下: $$ \def \arr #1#2#3#4#5#6#7#8{ \begin{bmatrix} #1 & #2 & #3 & #4\\ #5 & #6 & #7 & #8 \end{bmatrix} } \def \arrRow #1#2#3#4#5#6#7#8{ \begin{bmatrix} \mathbf{#1} & \mathbf{#2} & \mathbf{#3} & \mathbf{#4}\\ #5 & #6 & #7 & #8 \end{bmatrix} } \def \arrCol #1#2#3#4#5#6#7#8{ \begin{bmatrix} #1 & \mathbf{#2} & #3 & #4\\ #5 & \mathbf{#6} & #7 & #8 \end{bmatrix} } \def \toCol {\xrightarrow{\text{column, 2}}} \def \toRow {\xrightarrow{\text{row, 1}}} \begin{array}{cccccc} & \arr 13245678 & \toCol & \arrCol 16245378 & \toRow & \arrRow 42615378 \\ \toCol & \arrCol 43615278 & \toRow & \arrRow 16345278 & \toCol & \arrCol 12345678.\\ \end{array} $$ 对于样例的第三与第四组数据,目标矩阵 $b$ 为 $\begin{bmatrix}1&2\\3&4\\5&6\\7&8\end{bmatrix}$ 和 $\begin{bmatrix}1&2&3&4\\5&6&7&8\\9&10&11&12\\13&14&15&16\end{bmatrix}$,可以证明这两种情况均无解。