← 返回题目列表

AtCoder · tupc2023_d

D. 转变谜题

中文机器翻译题面 查看原题

配点 : {100} 点

問題文

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 匹配,如果可以匹配,则输出其中一种操作步骤。

制約

  • 2\leq N\leq 80
  • S_{x,y},T_{x,y} 是 您也可以写 # 或 至少 .
  • N 是一个整数

部分点

  • 附加限制 如果正确答案是满足 N\leq 4 的数据集 给出 10 点。 如果您正确回答了所有满足

入力

输入是按以下格式从标准输入给出的。

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 。

No

如果可能,请以以下格式输出操作步骤。

Yes
M
t_1 x_1
\vdots
t_M x_M

这里 M 表示操作次数, t_i,x_i 是 您也可以写 i 为第二次运算选择的整数 t,x 表示操作。它们需要满足以下条件。

  • 0\leq M\leq N^3
  • 1\leq t_i\leq 2
  • 1\leq x_i\leq N

入力例 1

3
.#.
#.#
.#.
#.#
...
#.#

出力例 1

Yes
4
1 3
2 3
2 1
1 1

S 如下所示变化:


入力例 2

3
.#.
#.#
.#.
.#.
#.#
.#.

出力例 2

Yes
0

一次操作都不执行。


入力例 3

13
.............
....#####....
......#......
......#......
......#......
......#......
.............
....#...#....
....#...#....
....#...#....
....#...#....
.....###.....
.............
....####.....
....#...#....
....####.....
....#........
....#........
.............
.....###.....
....#...#....
....#........
....#...#....
.....###.....
.............
.............

出力例 3

No