C - 随机

得分：$300$ 分

问题描述

给定由#和.组成的模式 $S$ 和 $T$，每个模式都具有 $H$ 行 $W$ 列。
将模式 $S$ 表示为 $H$ 个字符串，$S_i$ 的第 $j$ 个字符表示第 $i$ 行第 $j$ 列的元素。$T$ 同样如此。

确定是否可以通过重新排列 $S$ 的列将其变成 $T$。

这里，重新排列模式 $X$ 的列的方法如下。

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

其实就是重排 $S$ 的所有列的顺序，能否得到 $T$。

约束条件

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

输入

从标准输入中按以下格式给出输入：

$H$ $W$

$S_1$

$S_2$

$\vdots$

$S_H$

$T_1$

$T_2$

$\vdots$

$T_H$

输出

如果 $S$ 可以变成 $T$，输出 Yes；否则，输出 No。

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

Yes

例如，如果按照从左到右的顺序排列 $S$ 的第 $3$ 列，第 $4$ 列，第 $2$ 列和第 $1$ 列，$S$ 将等于 $T$。

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

No

在这个输入中，$S$ 无法变成 $T$。

2 1
#
.
#
.

Yes

$S=T$ 是可能的。

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

Yes