Score : $300$ points

问题描述

给定由#和.组成的模式$S$和$T$，每种模式都有$H$行和$W$列。
模式$S$以$H$个字符串的形式给出，其中$S_i$的第$j$个字符表示第$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$列的元素。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:44:19