← 返回题目列表

AtCoder · past202303_e

E. 随机播放形状

中文机器翻译题面 查看原题

问题陈述

给你数字 S 和 T 与 H 行和 W 列组成 # 和 ..
如图 S 给出为 H 字符串 S _ 1,S _ 2,\ldots,S _ H;的 j- 第一个字符 S _ i 表示位于 i第行和 j第 列 S。图 T 类似地给出。

确定是否可以重新排列每一行 S 使 S 等于 T.

在这里,重新排列图形的每一行 X 是以下操作。

  • 对于每个 i=1,2,\ldots,H,独立执行以下过程。
    • 选择一个排列 P=(P _ 1,P _ 2,\ldots,P _ W) of (1,2,\ldots,W).
    • 对于所有整数 j 这样 1 \leq j \leq W,同时替换 i第行和 j第 列 X 与那个在 i第行和 P_j第列。

请注意,您可以选择不同的排列 P 对于不同的 i.

约束

  • H 和 W 是整数。
  • 1 \leq H,W
  • 1 \leq H \times W \leq 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

输出

打印 Yes 如果可以的话 S 等于 T;打印 No 否则。


样本输入 1

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

示例输出 1

Yes

例如,如果您选择 (4,2,1,3),(1,3,4,2),(4,1,3,2) 为 i=1,2,3分别可以使 S 等于 T.


示例输入 2

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

示例输出 2

No

示例输入 3

2 1
#
.
#
.

示例输出 3

Yes

S=T 可能成立。


示例输入 4

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

示例输出 4

Yes