#P8929. [2020年省队模拟]网格上水题

    ID: 9022 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>算法基础构造数学模拟字符串搜索BFSCF2500

[2020年省队模拟]网格上水题

题目描述

小 Z 有一个 nn 行 mm 列的网格 SS,每个格子上有一个正整数。初始时,第 ii 行第 jj 列的格子中的正整数为 si,js_{i,j}。小 Z 希望通过一些操作得到一个第 ii 行第 jj 列的格子中的正整数为 ti,jt_{i,j} 的网格 TT。

小 Z 可以进行如下操作:

选定 mm 个正整数 p1,p2,…,pmp_1,p_2,\ldots,p_m(可以相同)和一个正整数 cc,满足 pi≤np_i\le n 且 c<mc<m。

假设当前网格第 ii 行第 jj 列的数为 ai,ja_{i,j},操作后得到的网格第 ii 行第 jj 列的数为 bi,jb_{i,j}。对于 1≤i≤n,1≤j≤m1\le i\le n,1\le j\le m:

  • 如果 i=pji=p_j,令 j′=(j+c−1) mod m+1j'=(j+c-1)\bmod m+1,则 bi,j=apj′,j′b_{i,j}=a_{p_{j'},j'};
  • 否则 bi,j=ai,jb_{i,j}=a_{i,j}。

你需要判断是否存在一个操作方案,使网格 SS 变为网格 TT。如果存在,请输出任意一个合法方案。

你最多只能进行 1600016000 次操作,不需要最小化操作次数。

为了避免过大的输出量,由于保证 n≤5n\le 5,每次操作中的 p1,p2,…,pmp_1,p_2,\ldots,p_m 用一个长度为 mm 的小写字符串表示,详见输出格式。

输入格式

第一行包含两个正整数 n,mn,m。

接下来 nn 行,每行包含 mm 个正整数,第 ii 行第 jj 个整数表示 si,js_{i,j}。

再接下来 nn 行,每行包含 mm 个正整数,第 ii 行第 jj 个整数表示 ti,jt_{i,j}。

输出格式

第一行输出字符串 Yes 或 No,表示是否存在把网格 SS 变为网格 TT 的合法操作方案。

如果输出 No,不需要再输出其他内容。

如果输出 Yes,第二行输出一个非负整数 CC,表示操作次数,要求 0≤C≤160000\le C\le 16000。

接下来 CC 行,每行输出一个正整数 dd 和一个长度为 mm 的字符串 oo,表示一次 c=dc=d 的操作。对于 1≤i≤m1\le i\le m,令 pip_i 等于 oio_i 的 ASCII 码减去 9696。

因此,为保证操作合法,必须满足:

  • 1≤d<m1\le d<m;
  • 字符串 oo 的长度恰好为 mm;
  • 对于每个字符 oio_i,都有 1≤ASCII⁡(oi)−96≤n1\le \operatorname{ASCII}(o_i)-96\le n。

推荐使用字符串整体输出,不要逐字符输出。

样例 1

输入

1 5
1 2 3 4 5
5 4 3 2 1

输出

No

样例 2

输入

2 2
1 2
3 4
4 3
2 1

输出

Yes
2
1 ab
1 ba

说明

这不是唯一的合法方案。

样例 3

输入

2 1
1
2
2
1

输出

No

样例 4

输入

2 3
1 2 3
4 5 6
5 2 1
4 3 6

输出

Yes
1
1 aba

说明

这也不是唯一的合法方案。

数据范围

对于所有数据:

  • 1≤n≤51\le n\le 5;
  • 1≤m≤10001\le m\le 1000;
  • 1≤si,j,ti,j≤1091\le s_{i,j},t_{i,j}\le 10^9。
子任务 分值 限制
1 5 n=1n=1
2 10 1≤nm≤81\le nm\le 8
3 15 1≤nm≤701\le nm\le 70
4 20 1≤nm≤10001\le nm\le 1000
5 m≤500m\le 500
6 30 无特殊限制,依赖子任务 1、2、3、4、5