Problem:


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



Sample input:
2 3
arc
rac


Sample output:
YES

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    h, w = f.read_int_list()
    s = [list(f.read_str()) for i in xrange(h)]

    sh = sorted(["".join(sorted(si)) for si in s])
    sw = sorted(["".join(sorted([s[hi][wi] for hi in xrange(h)])) for wi in xrange(w)])

    odd_h = []
    dh = collections.Counter(sh)
    for k, v in dh.items():
        if v % 2 == 1: odd_h.append(k)

    odd_w = []
    dw = collections.Counter(sw)
    for k, v in dw.items():
        if v % 2 == 1: odd_w.append(k)

    if len(odd_h) > h % 2 or len(odd_w) > w % 2: return "NO"

    if len(odd_h) == 1 and len(odd_w) == 1:
        if odd_h[(w+1)/2] != odd_w[(h+1)/2]:
            return "NO"
    if len(odd_h) == 1:
        if odd_h[0][:w/2] != odd_h[0][(w+1)/2:]:
            return "NO"
    if len(odd_w) == 1:
        if odd_w[0][:h/2] != odd_w[0][(h+1)/2:]:
            return "NO"

    return "YES"


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())

def str2int_array(x):
    return ord(x) - ord('a')

import numpy as np

X = np.array([list(map(str2int_array, input())) for _ in range(H)])
columns = np.copy(X).T
lines = X
lines.sort(1)
columns.sort(1)

checked = [False] * H
for i in range(H):
    if checked[i]:
        continue
    l1 = lines[i]
    for j in range(i+1, H):
        if checked[j]:
            continue
        l2 = lines[j]
        if np.linalg.norm(l1 -l2) == 0:
            checked[i] = True
            checked[j] = True
            break
if len(list(filter(lambda i : not checked[i], range(H)))) > 1:
    print("NO")
    exit()


checked = [False] * W
for i in range(W):
    if checked[i]:
        continue
    l1 = columns[i]
    for j in range(i+1, W):
        if checked[j]:
            continue
        l2 = columns[j]
        if np.linalg.norm(l1 -l2) == 0:
            checked[i] = True
            checked[j] = True
            break
if len(list(filter(lambda i : not checked[i], range(H)))) > 1:
    print("NO")
    exit()

print("YES")