← 返回题目列表

AtCoder · abc279_c

E. 随机

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

分数: 300 点

问题陈述

给定了模式 S 和 T 组成 # 和 .,每个都有 H 行和 W 列。
模式 S 给出为 H 字符串,以及 j- 第一个字符 S_i 表示位于 i第行和 j- 第列。同样适用于 T.

判断是否 S 可以等于 T 通过重新排列列 S.

此处,重新排列模式的列 X 的完成方式如下。

  • 选择一个排列 P=(P_1,P_2,\dots,P_W) of (1,2,\dots,W).
  • 然后,对于每个整数 i 这样 1 \le i \le H,同时执行以下操作。
    • 对于每个整数 j 这样 1 \le j \le W,同时替换 i第行和 j第 列 X 元素位于 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

输出

If S 可以等于 T,打印 Yes;否则,打印 No.


示例输入 1

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

示例输出 1

Yes

例如,如果您安排 3-rd, 4-th, 2-nd,和 1-st 列 S 按从左到右的顺序, S 将等于 T.


示例输入 2

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

示例输出 2

No

在此输入中, S 不能等于 T.


示例输入 3

2 1
#
.
#
.

示例输出 3

Yes

有可能 S=T.


示例输入 4

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

示例输出 4

Yes