AT_past202303_e.図形のシャッフル

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定两个由 $H$ 行 $W$ 列、仅包含字符 # 和 . 的图形 $S$ 和 $T$ 。
图形 $S$ 由 $H$ 个字符串 $S_1, S_2, \ldots, S_H$ 给出，其中 $S_i$ 的第 $j$ 个字符表示 $S$ 的第 $i$ 行第 $j$ 列的元素。图形 $T$ 也以类似方式给出。

请判断是否可以通过重新排列 $S$ 的每一行，使 $S$ 变为 $T$ 。

对于图形 $X$ 的每一行的重排操作如下：

对于每个 $i=1,2,\ldots,H$ $i = 1, 2, \dots, H$ ，各自独立进行以下操作：
- 选择 $(1,2,\ldots,W)$ 的一个排列 $P=(P_1,P_2,\ldots,P_W)$ 。
- 对于所有 $1\leq j\leq W$ 的整数，同时将 $X$ 的第 $i$ 行第 $j$ 列的元素替换为第 $i$ 行第 $P_j$ 列的元素。

注意，不同的 $i$ 可以选择不同的排列 $P$ 。

输入格式

输入从标准输入读入，格式如下：

$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
```
输入#2
```
3 4
#...
#..#
.###
..##
#..#
##..
```
输出#2
```
No
```
输入#3
```
2 1
#
.
#
.
```
输出#3
```
Yes
```

输入#4

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

输出#4

Yes

说明/提示

样例解释 1

例如，对于 $i=1,2,3$ ，分别选择排列 $(4,2,1,3)$ 、 $(1,3,4,2)$ 、 $(4,1,3,2)$ ，就可以将 $S$ 变为 $T$ 。

样例解释 3

也可能出现 $S=T$ 的情况。

约束条件

$H$ 和 $W$ 均为整数。
$1 \leq H, W$ 。
$1 \leq H \times W \leq 4 \times 10 ^ 5$ 。
$S_i$ 和 $T_i$ 均为仅包含 # 和 . 的长为 $W$ 的字符串。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页