/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
# と . からなる H 行 W 列の図形 S,T が与えられます。
図形 S は H 個の文字列として与えられ、 S_i の j 文字目は S の 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 列にある要素に置き換える。
制約
- 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
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