102792: [AtCoder]ABC279 C - RANDOM
Description
Score : $300$ points
Problem Statement
You are given patterns $S$ and $T$ consisting of # and ., each with $H$ rows and $W$ columns.
The pattern $S$ is given as $H$ strings, and the $j$-th character of $S_i$ represents the element at the $i$-th row and $j$-th column. The same goes for $T$.
Determine whether $S$ can be made equal to $T$ by rearranging the columns of $S$.
Here, rearranging the columns of a pattern $X$ is done as follows.
- Choose a permutation $P=(P_1,P_2,\dots,P_W)$ of $(1,2,\dots,W)$.
- Then, for every integer $i$ such that $1 \le i \le H$, simultaneously do the following.
- For every integer $j$ such that $1 \le j \le W$, simultaneously replace the element at the $i$-th row and $j$-th column of $X$ with the element at the $i$-th row and $P_j$-th column.
Constraints
- $H$ and $W$ are integers.
- $1 \le H,W$
- $1 \le H \times W \le 4 \times 10^5$
- $S_i$ and $T_i$ are strings of length $W$ consisting of
#and..
Input
The input is given from Standard Input in the following format:
$H$ $W$ $S_1$ $S_2$ $\vdots$ $S_H$ $T_1$ $T_2$ $\vdots$ $T_H$
Output
If $S$ can be made equal to $T$, print Yes; otherwise, print No.
Sample Input 1
3 4 ##.# ##.. #... .### ..## ...#
Sample Output 1
Yes
If you, for instance, arrange the $3$-rd, $4$-th, $2$-nd, and $1$-st columns of $S$ in this order from left to right, $S$ will be equal to $T$.
Sample Input 2
3 3 #.# .#. #.# ##. ##. .#.
Sample Output 2
No
In this input, $S$ cannot be made equal to $T$.
Sample Input 3
2 1 # . # .
Sample Output 3
Yes
It is possible that $S=T$.
Sample Input 4
8 7 #..#..# .##.##. #..#..# .##.##. #..#..# .##.##. #..#..# .##.##. ....### ####... ....### ####... ....### ####... ....### ####...
Sample Output 4
Yes
Input
题意翻译
【题目翻译】 给定两个 $n$ 行 $m$ 列的矩阵 $A$ 与 $B$，你可以多次交换任意两列，求 $A$ 能否变成 $B$。 translated by @[liangbowen](https://www.luogu.com.cn/user/367488)。Output
问题描述
给定由'#'和'.'组成的模式$S$和$T$，每行有$H$个元素，每列有$W$个元素。
$S$由$H$个字符串给出，$S_i$的第$j$个字符表示第$i$行第$j$列的元素。$T$也是一样。
确定是否可以通过重新排列$S$的列使得$S$等于$T$。
重新排列一个模式$X$的列的方法如下。
- 选择一个排列$P=(P_1,P_2,\dots,P_W)$，其中$(1,2,\dots,W)$。
- 然后，对于满足$1 \le i \le H$的每个整数$i$，同时执行以下操作。
- 对于满足$1 \le j \le W$的每个整数$j$，同时将$X$中第$i$行第$j$列的元素替换为第$i$行第$P_j$列的元素。
约束条件
- $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。
样例输入1
3 4 ##.# ##.. #... .### ..## ...#
样例输出1
Yes
例如，如果将$S$的第3列，第4列，第2列和第1列按从左到右的顺序排列，$S$将等于$T$。
样例输入2
3 3 #.# .#. #.# ##. ##. .#.
样例输出2
No
在这个输入中，$S$不能等于$T$。
样例输入3
2 1 # . # .
样例输出3
Yes
有可能$S=T$。
样例输入4
8 7 #..#..# .##.##. #..#..# .##.##. #..#..# .##.##. #..#..# .##.##. ....### ####... ....### ####... ....### ####... ....### ####...
样例输出4
Yes