Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 700 点
問題文
H 行 W 列のマス目があり,各マスには英小文字が書かれています. 具体的には,上から i 行,左から j 列目のマスに書かれている文字は,文字列 S_i の j 文字目に等しいです.
すぬけ君は,このマス目に対して次の操作を好きな回数行うことができます:
- 2 つの異なる行を選び,入れ替える.または,2 つの異なる列を選び,入れ替える.
すぬけ君は,このマス目が点対称的になるようにしたいです. すなわち,任意の 1 \leq i \leq H, 1 \leq j \leq W に対して,マス目の上から i 行,左から j 列目に書かれている文字と,マス目の上から H + 1 - i 行,左から W + 1 - j 列目に書かれている文字が等しくなるようにしたいです.
すぬけくんがこの目標を達成することが可能かどうか判定してください.
制約
- 1 \leq H \leq 12
- 1 \leq W \leq 12
- |S_i| = W
- S_i は英小文字のみからなる
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 : S_H
出力
マス目を点対称的にできるなら YES
を,できないなら NO
を出力せよ.
入力例 1
2 3 arc rac
出力例 1
YES
下の画像に示すように,左から 2 列目と 3 列目を入れ替えると,マス目が点対称的になります.
入力例 2
3 7 atcoder regular contest
出力例 2
NO
入力例 3
12 12 bimonigaloaf faurwlkbleht dexwimqxzxbb lxdgyoifcxid ydxiliocfdgx nfoabgilamoi ibxbdqmzxxwe pqirylfrcrnf wtehfkllbura yfrnpflcrirq wvcclwgiubrk lkbrwgwuiccv
出力例 3
YES
Score : 700 points
Problem Statement
There is an H \times W grid (H vertical, W horizontal), where each square contains a lowercase English letter. Specifically, the letter in the square at the i-th row and j-th column is equal to the j-th character in the string S_i.
Snuke can apply the following operation to this grid any number of times:
- Choose two different rows and swap them. Or, choose two different columns and swap them.
Snuke wants this grid to be symmetric. That is, for any 1 \leq i \leq H and 1 \leq j \leq W, the letter in the square at the i-th row and j-th column and the letter in the square at the (H + 1 - i)-th row and (W + 1 - j)-th column should be equal.
Determine if Snuke can achieve this objective.
Constraints
- 1 \leq H \leq 12
- 1 \leq W \leq 12
- |S_i| = W
- S_i consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
H W S_1 S_2 : S_H
Output
If Snuke can make the grid symmetric, print YES
; if he cannot, print NO
.
Sample Input 1
2 3 arc rac
Sample Output 1
YES
If the second and third columns from the left are swapped, the grid becomes symmetric, as shown in the image below:
Sample Input 2
3 7 atcoder regular contest
Sample Output 2
NO
Sample Input 3
12 12 bimonigaloaf faurwlkbleht dexwimqxzxbb lxdgyoifcxid ydxiliocfdgx nfoabgilamoi ibxbdqmzxxwe pqirylfrcrnf wtehfkllbura yfrnpflcrirq wvcclwgiubrk lkbrwgwuiccv
Sample Output 3
YES