Problem: 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.

Submission attempts (in order):
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
T = [[None]*H for i in range(W)]
D = {}
for i in range(H):
    for j in range(W):
        c = S[i][j]
        D[c] = D.get(c, 0) ^ 1
if sum(D.values()) != (1 if (H%2==1)and(W%2==1) else 0):
    print("NO")
    exit(0)
for i in range(H):
    s = S[i]
    for j in range(W):
        T[j][i] = s[j]
def check(S, H, W):
    res = []
    ok1 = 1
    for p in range(H):
        sp = S[p]
        for q in range(p+1, H):
            sq = S[q]
            d = {}
            for k in range(W):
                if sp[k] < sq[k]:
                    k = sp[k], sq[k]
                    d[k] = d.get(k, 0) + 1
                elif sp[k] == sq[k]:
                    k = sp[k], sp[k]
                    d[k] = d.get(k, 0) ^ 1
                else:
                    k = sq[k], sp[k]
                    d[k] = d.get(k, 0) - 1
            cap = (W % 2)
            ok = 1
            for a, b in d:
                if a == b:
                    if d[a, b]:
                        if cap == 0:
                            ok = ok1 = 0
                        cap -= 1
                else:
                    if d[a, b] != 0:
                        ok = ok1 = 0
            if ok: res.append((p, q))
    if H % 2 == 1:
        for p in range(H):
            d = {}
            for s in S[p]:
                d[s] = d.get(s, 0) ^ 1
            if sum(d.values()) == W % 2:
                res.append((p, p))
    return [] if ok1 else res
sc = check(S, H, W)
tc = check(T, W, H)
def solve(N, P):
    def dfs(state, c):
        if N == c:
            return 1
        for p, q in P:
            v = (1 << p) | (1 << q)
            if state & v:
                continue
            if dfs(state | v, (c+2 if p != q else c+1)):
                return 1
        return 0
    return dfs(0, 0)
if solve(H, sc) and solve(W, tc):
    print("YES")
else:
    print("NO")



H, W = map(int, input().split())
S = [input() for i in range(H)]

def check(l):
    u = [0]*W
    mid = W % 2
    for i in range(W):
        if u[i]:
            continue
        for j in range(i+1, W):
            for p, q in l:
                sp = S[p]; sq = S[q]
                if sp[i] != sq[j] or sp[j] != sq[i]:
                    break
            else:
                u[j] = 1
                break
        else:
            if mid:
                for p, q in l:
                    sp = S[p]; sq = S[q]
                    if sp[i] != sq[i]:
                        break
                else:
                    mid = 0
                    continue
            break
    else:
        return 1
    return 0

def make(c, l, u, p):
    while c in u:
        c += 1
    if c == H:
        if check(l):
            print("YES")
            exit(0)
        return
    if p:
        l.append((c, c))
        make(c+1, l, u, 0)
        l.pop()
    for i in range(c+1, H):
        if i in u:
            continue
        u.add(i)
        l.append((c, i))
        make(c+1, l, u, p)
        l.pop()
        u.remove(i)

make(0, [], set(), H%2)
print("NO")

Verdicts: Wrong Answer

Accepted