D - Shift Puzzle
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : {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 1 2 3 1 1
S は以下のように変化します。
入力例 2
3 .#. #.# .#. .#. #.# .#.
出力例 2
Yes 0
一度も操作を行いません。
入力例 3
13 ............. ....#####.... ......#...... ......#...... ......#...... ......#...... ............. ....#...#.... ....#...#.... ....#...#.... ....#...#.... .....###..... ............. ....####..... ....#...#.... ....####..... ....#........ ....#........ ............. .....###..... ....#...#.... ....#........ ....#...#.... .....###..... ............. .............
出力例 3
No