AT_abc279_c [ABC279C] RANDOM

题目描述

给定由 # 和 . 组成的 $H$ 行 $W$ 列的两个图形 $S$ 和 $T$。
图形 $S$ 以 $H$ 个字符串的形式给出，第 $i$ 个字符串 $S_i$ 的第 $j$ 个字符表示 $S$ 的第 $i$ 行第 $j$ 列的元素。$T$ 也以同样方式给出。

请判断是否可以通过重新排列 $S$ 的列，使其与 $T$ 完全相同。

这里，重新排列图形 $X$ 的列指的是以下操作：

• 选择一个 $1,2,\dots,W$ 的排列 $P=(P_1,P_2,\dots,P_W)$。
• 然后，对于所有满足 $1\le i\le H$ 的整数 $i$，同时进行如下操作：
  • 对于所有满足 $1\le j\le W$ 的整数 $j$，同时将 $X$ 的第 $i$ 行第 $j$ 列的元素替换为第 $i$ 行第 $P_j$ 列的元素。

输入格式

输入以如下格式从标准输入读入。

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$
$T_1$
$T_2$
$\vdots$
$T_H$

输出格式

如果可以通过重新排列 $S$ 的列使其与 $T$ 完全相同，则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

3 4
##.#
##..
#...
.###
..##
...#

输出 #1

Yes

输入输出样例 #2

输入 #2

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

输出 #2

No

输入输出样例 #3

输入 #3

2 1
#
.
#
.

输出 #3

Yes

输入输出样例 #4

输入 #4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

输出 #4

Yes

说明/提示

限制条件

• $H,W$ 为整数。
• $1\le H,W$。
• $1\le H\times W\le 4\times 10^5$。
• $S_i,T_i$ 是由 # 和 . 组成的长度为 $W$ 的字符串。

样例解释 1

例如，将 $S$ 的第 3、4、2、1 列按此顺序从左到右排列时，可以使 $S$ 与 $T$ 完全相同。

样例解释 2

在此输入中，无法使 $S$ 与 $T$ 完全相同。

样例解释 3

也有可能 $S=T$。

由 ChatGPT 4.1 翻译