← 返回题目列表

AtCoder · arc095_c

E. 对称网格

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

分数: 700 点

问题陈述

有一个 H \times W 网格(H 垂直, W 水平),其中每个方块包含一个小写英文字母。 具体来说,正方形中的字母 i第行和 j第列等于 j- 字符串中的第一个字符 S_i.

Snuke 可以多次对该网格应用以下操作:

  • 选择两个不同的行并交换它们。或者,选择两个不同的列并交换它们。

Snuke 希望这个网格是 对称。 也就是说,对于任意 1 \leq i \leq H 和 1 \leq j \leq W,位于方框中的字母 i第行和 j第列和方框中的字母 (H + 1 - i)第行和 (W + 1 - j)第列应该相等。

确定 Snuke 是否可以实现这一目标。

约束

  • 1 \leq H \leq 12
  • 1 \leq W \leq 12
  • |S_i| = W
  • S_i 由小写英文字母组成。

输入

输入由标准输入按以下格式给出:

H W
S_1
S_2
:
S_H

输出

如果 Snuke 可以使网格对称,则打印 YES;如果他不能,请打印 NO.


示例输入 1

2 3
arc
rac

示例输出 1

YES

如果交换左起第二列和第三列,则网格变得对称,如下图所示:


示例输入 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