RANDOM

题目描述

你被给定由 # 和 $.$ 组成的模式 $S$ 和 $T$，每个有 $H$ 行和 $W$ 列。
模式 $S$ 作为 $H$ 个字符串给出，且 $S_i$ 的第 $j$ 个字符表示第 $i$ 行第 $j$ 列的元素。$T$ 亦然。 判定是否可以通过重新排列 $S$ 的列使 $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$ 行第 $P_j$ 列的元素替换 $X$ 的第 $i$ 行第 $j$ 列的元素。

输入格式

输入从标准输入按以下格式给出： $H$ $W$ $S_1$ $S_2$ $\vdots$ $S_H$ $T_1$ $T_2$ $\vdots$ $T_H$

输出格式

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

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

Yes

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

No

2 1
#
.
#
.

Yes

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

Yes

提示

$H$ 和 $W$ 是整数。 $1 \le H,W$ $1 \le H \times W \le 4 \times 10^5$ $S_i$ 和 $T_i$ 是由 # 和 $.$ 组成的长度为 $W$ 的字符串。例如，如果你将 $S$ 的第 $3$、第 $4$、第 $2$、第 $1$ 列按此顺序从左到右排列，$S$ 将等于 $T$。
在该输入中，无法将 $S$ 变为 $T$。
可能存在 $S=T$。

标签: AtCoder|abc279C

来源

AtCoder|abc279C