AT_tupc2023_d Shift Puzzle

给定两个 $N\times N$ 的方格，分别为 $S$ 和 $T$，每个格子被染成黑色或白色。每个方格的状态用 $N^2$ 个字符来表示，对于 $S$ 来说，第 $x$ 行第 $y$ 列的格子如果是黑色，$S_{x,y}$ 为 `#`，如果是白色，$S_{x,y}$ 为 `.`，$T$ 的定义方式同理。 你可以对方格 $S$ 进行如下操作： - 选择整数 $t,x$（$1\leq t\leq 2,1\leq x\leq N$）。 - 当 $t=1$ 时，将 $S$ 第 $x$ 行的所有格子的颜色向右循环平移 $1$ 格。即 $S_{x,1}S_{x,2}\ldots S_{x,N}$ 变为 $S_{x,N}S_{x,1}\ldots S_{x,N-1}$。 - 当 $t=2$ 时，将 $S$ 第 $x$ 列的所有格子的颜色向下循环平移 $1$ 格。即 $S_{1,x}S_{2,x}\ldots S_{N,x}$ 变为 $S_{N,x}S_{1,x}\ldots S_{N-1,x}$。 你需要判断，是否可以用不超过 $N^3$ 次操作将 $S$ 变换为 $T$，如果可以，输出一种操作方案。

输入从标准输入读入，格式如下： > $N$ > $S_{1,1}\ldots S_{1,N}$ > $\vdots$ > $S_{N,1}\ldots S_{N,N}$ > $T_{1,1}\ldots T_{1,N}$ > $\vdots$ > $T_{N,1}\ldots T_{N,N}$

如果无法通过不超过 $N^3$ 次操作使两个方格一致，输出： ``` No ``` 如果可以，输出以下格式的操作方案： > Yes > $M$ > $t_1$ $x_1$ > $\vdots$ > $t_M$ $x_M$ 其中 $M$ 为操作次数，$t_i,x_i$ 为第 $i$ 次操作的选取，每组数据应满足： - $0\leq M\leq N^3$ - $1\leq t_i\leq 2$ - $1\leq x_i\leq N$

### 部分分 对于满足附加限制 $N\leq 4$ 的测试数据，得分为 $10$ 分。 ### 样例说明 1 $S$ 会按如下方式变化：  ### 样例说明 2 一次操作都不需要。 # 数据范围 - $2 \leq N \leq 80$ - $S_{x,y}$、$T_{x,y}$ 均为 `#` 或 `.` - $N$ 为整数。 由 ChatGPT 5 翻译