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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

orda = ord('a')
p12 = 2 ** 12

s = None
ts = None
h = None
w = None

row_keys = None
col_keys = None


def calc_row_keys(sel = 0, count = 0, last = -1):
    if count == w // 2:
        arr = []
        row_keys[sel] = arr
        for i in range(h):
            si = s[i]
            ss = []
            for j in range(w):
                if sel & (2 ** j):
                    ss.append(si[j])
            ss.sort()
            v = 0
            for ch in ss:
                v *= 26
                v += ord(ch) - orda
            arr.append(v)
    else:
        for j in range(last + 1, w):
            calc_row_keys(sel | (2 ** j), count + 1, j)


def calc_col_keys(sel = 0, count = 0, last = -1):
    if count == h // 2:
        arr = []
        col_keys[sel] = arr
        for j in range(w):
            sj = ts[j]
            ss = []
            for i in range(h):
                if sel & (2 ** i):
                    ss.append(sj[i])
            ss.sort()
            v = 0
            for ch in ss:
                v *= 26
                v += ord(ch) - orda
            arr.append(v)
    else:
        for i in range(last + 1, h):
            calc_col_keys(sel | (2 ** i), count + 1, i)


def check_sym1(t):
    c = 0
    for ch in t:
        c ^= 2 ** (ord(ch) - orda)
    odd = 0
    for code in range(26):
        if c & (2 ** code):
            odd += 1
    return odd <= 1


def check_sym(sel_rows, sel_rows2, center_row = None, sel_cols = None, sel_cols2 = None, center_col = None):
    if sel_cols is None:
        t0 = 2 ** w - 1
        if w % 2:
            for j in range(w):
                p2j = 2 ** j
                t = t0 - p2j
                for sel_cols in row_keys.keys():
                    if sel_cols & p2j:
                        continue
                    sel_cols2 = t - sel_cols
                    if sel_cols2 < sel_cols:
                        continue
                    if check_sym(sel_rows, sel_rows2, center_row, sel_cols, sel_cols2, j):
                        return True
            return False
        else:
            for sel_cols in row_keys.keys():
                sel_cols2 = t0 - sel_cols
                if sel_cols2 < sel_cols:
                    continue
                if check_sym(sel_rows, sel_rows2, center_row, sel_cols, sel_cols2):
                    return True
            return False
    else:
        rows = []
        rows2 = []
        keys = row_keys[sel_cols]
        keys2 = row_keys[sel_cols2]
        sc = None
        if center_col is not None:
            sc = ts[center_col]
        for i in range(h):
            p2i = 2 ** i
            k = 0 if sc is None else (ord(sc[i]) - orda)
            if p2i & sel_rows:
                k += (keys[i] * p12 + keys2[i]) * 32
                rows.append((k, i))
            elif p2i & sel_rows2:
                k += (keys2[i] * p12 + keys[i]) * 32
                rows2.append((k, i))
        rows.sort()
        rows2.sort()
        for i in range(len(rows)):
            if rows[i][0] != rows2[i][0]:
                return False
        if center_col is not None:
            sc = ts[center_col]
            for i in range(len(rows)):
                if sc[rows[i][1]] != sc[rows2[i][1]]:
                    return False
        cols = []
        cols2 = []
        keys = col_keys[sel_rows]
        keys2 = col_keys[sel_rows2]
        sc = None
        if center_row is not None:
            sc = s[center_row]
        for j in range(w):
            p2j = 2 ** j
            k = 0 if sc is None else (ord(sc[j]) - orda)
            if p2j & sel_cols:
                k += (keys[j] * p12 + keys2[j]) * 32
                cols.append((k, j))
            elif p2j & sel_cols2:
                k += (keys2[j] * p12 + keys[j]) * 32
                cols2.append((k, j))
        cols.sort()
        cols2.sort()
        for j in range(len(cols)):
            if cols[j][0] != cols2[j][0]:
                return False
        if center_row is not None:
            sc = s[center_row]
            for j in range(len(cols)):
                if sc[cols[j][1]] != sc[cols2[j][1]]:
                    return False
        for i in range(len(rows)):
            si = s[rows[i][1]]
            si2 = s[rows2[i][1]]
            for j in range(len(cols)):
                if si[cols[j][1]] != si2[cols2[j][1]]:
                    return False
                if si[cols2[j][1]] != si2[cols[j][1]]:
                    return False

    return True


def solve():
    global row_keys, col_keys
    global ts

    if h == 1 or w == 1:
        if h == 1:
            s0 = s[0]
        else:
            s0 = ''.join(s)
        return check_sym1(s0)

    ts = ['' for _ in range(w)]
    for i in range(h):
        si = s[i]
        for j in range(w):
            ts[j] += si[j]

    row_keys = {}
    col_keys = {}
    calc_row_keys()
    calc_col_keys()

    t0 = 2 ** h - 1
    if h % 2:
        for i in range(h):
            p2i = 2 ** i
            t = t0 - p2i
            for sel_rows in col_keys.keys():
                if sel_rows & p2i:
                    continue
                sel_rows2 = t - sel_rows
                if sel_rows2 < sel_rows:
                    continue
                if check_sym(sel_rows, sel_rows2, i):
                    return True
    else:
        for sel_rows in col_keys.keys():
            sel_rows2 = t0 - sel_rows
            if sel_rows2 < sel_rows:
                continue
            if check_sym(sel_rows, sel_rows2):
                return True

    return False


def main():
    global s, h, w

    h, w = input().split()
    h = int(h)
    w = int(w)
    s = [input() for _ in range(h)]


    print('YES' if solve() else 'NO')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Regular Contest 95
Author     : Kitaura Hiromi
LastUpdate : 20180416
Since      : 20180416
"""

import numpy as np

def check_symmetric_by_cols_rearange(cols):
    center_flag = False
    while len(cols) != 0:
        col = cols.pop()
        upsidedown_col = col[::-1]
        if upsidedown_col in cols:
            cols.pop(cols.index(upsidedown_col))
        else:
            if W%2 == 0:
                return False
            elif col == upsidedown_col and center_flag is False:
                center_flag = True
                continue
            else:
                return False
    return True


def dfs(S, T, Num):
    ans = False
    if Num == H:
        return check_symmetric_by_cols_rearange(list(zip(*rows[T])))
    else:
        for i in range(H - Num):
            ans = ans or dfs(S[:i]+S[i+1:], T+[S[i]], Num+1)
    return ans

H, W = map(int, input().split(" "))
rows = []
for h in range(H):
    rows.append(input())
rows = np.array(rows)

if dfs(list(range(H)), [], 0):
    print("YES")
else:
    print("NO")

Submission status: Time Limit Exceeded

Solution code:
# E
import numpy as np

H, W = map(int, input().split())
S = list()
for _ in range(H):
    S.append(list(input()))
S_arr = np.array(S)

res = "NO"

def check_col_switch(S_arr, H, W):
    if W % 2 == 1:
        res_bar = -1
    else:
        res_bar = 0
    done_col = np.zeros(W)
    for j in range(W):
        if done_col[j] == 1:
            continue
        rev_j = S_arr[::(-1), j]
        for k in range(W):
            if np.prod(S_arr[:, k] == rev_j) == 1 and j != k and done_col[k] == 0:
                done_col[j] = 1
                done_col[k] = 1
                break
        if done_col[j] == 0:
            if np.prod(S_arr[:, j] == rev_j) == 1:
                done_col[j] = 1
                res_bar += 1
            else:
                res_bar += 10
    if res_bar <= 0:
        return "YES"
    else:
        return "NO"
    
    
def make_pairs(x_list):
    if len(x_list) <= 2:
        return [[x_list]]
    else:
        res = []
        for j in range(1, len(x_list)):
            x_list_s = [x_list[k] for k in range(1, len(x_list)) if k != j]
            res = res + [[[x_list[0], x_list[j]]] + xl for xl in make_pairs(x_list_s)]
        if len(x_list) % 2 == 1:
            x_list_l = [x_list[k] for k in range(1, len(x_list))]
            res = res + [xl + [[x_list[0]]] for xl in make_pairs(x_list_l)]
        return res
    
def run_row_switch(S_arr, row_matching, H, W):
    S_arr_row = S_arr.copy()
    i = 0
    for mat in row_matching:
        if len(mat) == 2:
            S_arr_row[i, :] = S_arr[mat[0], :]
            S_arr_row[H-1-i, :] = S_arr[mat[1], :]
            i += 1
        else:
            S_arr_row[(H-1)//2, :] = S_arr[mat[0], :]
    return S_arr_row
            
row_match_list = make_pairs([i for i in range(H)])

for rs in row_match_list:
    res = check_col_switch(run_row_switch(S_arr, rs, H, W), H, W)
    if res == "YES":
        break
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

h, w = map(int, input().split())
s = [None] * h
ss = [None] * h
for i in range(h):
    s[i] = input()
    ss[i] = sorted(s[i])

def c(x, y):
    l = len(y)
    if l == w: return True
    if l % 2 == 0:
        for i in range(w):
            if i not in y:
                y.append(i)
                if c(x, y): return True
                y.pop()
    else:
        for i in range(w):
            if i not in y:
                ok = True
                for j in range(0, h, 2):
                    if j + 1 == h: k = j
                    else: k = j + 1
                    a, b = x[j], x[k]
                    d, e = y[-1], i
                    if s[a][d] == s[b][e] and s[a][e] == s[b][d]:
                        continue
                    ok = False
                if ok:
                    y.append(i)
                    if c(x, y): return True
                    y.pop()
    return False
    
def r(x):
    l = len(x)
    if l == h:
        for i in range(w):
            if c(x, [i]): return True
    if l % 2 == 0:
        for i in range(h):
            if i not in x:
                x.append(i)
                if r(x): return True
                x.pop()
    else:
        for i in range(h):
            if i not in x and ss[x[-1]] == ss[i]:
                x.append(i)
                if r(x): return True
                x.pop()
    return False
            

ok = True
for i in range(h):
    ok = r([i])
    if ok: break
if ok: print('YES')
else: print('NO')

Submission status: Accepted

Solution code:
"""

https://atcoder.jp/contests/arc095/tasks/arc095_c

列、行の文字の組み合わせは変わらない
→対応する列・行の組み合わせがなければだめ

→では、各組み合わせが2こずつちゃんとあれば必ず可能か…？
→だとしたら制約小さすぎない？？

ab
ba

abc
aba
cba

→多分十分条件ではないけど少なくとも各組み合わせが2こない場合は絶対×
→かつ、端数の文字が1こ以下でないとだめ
ダメな場合はなんだーーー

分からないけど探索すればよさそう
→ペアになる列・行さえ決まればいい

(11*9*7*5*3*1)**2　→ 10^8ぐらい　最大12**2回探索するので…ア
1ms解法は何…

あらかじめありうるペアだけ列挙しておく？
→あとの入れ替えは探索

→最大になるような場合は全部同じ場合なのですぐ答えが見つかる…と信じたい

1234
2341
3412
4123 →このパターンの場合最悪計算量になってしまう…

1234
2341
4123
3412

1243
2314
4132
3421→ok…？

必要十分条件なのか…？　700点だし…？

反例:
12Z34
23Y41
ZYXYZ
41Y23
34Z12


どうやら現実的な時間で解けるらしい
ちゃんと考えよう
→入れ替えた際に保持されるパラメータを考える…？

答えに対し、対称な列と行を入れ替えても問題ない
& 対称な列のset/行のsetを入れ替えても問題ない
→すなわち列・行の対応以外は全く関係ない

=====答えを見た=====
片側だけペアにするのか…
→確かに片側全探索したらもう片方は簡単に判定できる…(裏返しがあるか判定するだけなので)

具体的な実装は…
まずペアを列挙→再帰で適当にやる
→列を入れ替えたとする

次に横で見てって、各ペアの数字が全て対になってる物があるか調べればいい
→ペア通り数 * H * H * W
"""

def pair(end,lis):
    if len(lis) == 0:
        p.append(end)
        return
    else:
        end.append(lis[0])
        del lis[0]
        for j in range(len(lis)):
            pair( end+[lis[j]] , lis[:j]+lis[j+1:])

from sys import stdin
import sys

H,W = map(int,stdin.readline().split())

S = []
for i in range(H):
    s = stdin.readline()
    S.append(s[:-1])
#print (S)

#ペア列挙
p = []
if W % 2 == 0:
    pair([],[i for i in range(W)])
else:
    tmp = [i for i in range(W)]
    for i in range(W):
        pair([i,i] , tmp[:i] + tmp[i+1:])

#print (p)

for pl in p:
    able = [True] * H
    flag = 0

    for i in range(H):
        if able[i]:
            for j in range(i+1,H):
                if not able[j]:
                    continue

                tmpf = True
                for w in range((W+1)//2):
                    if S[i][pl[2*w]] != S[j][pl[2*w+1]] or S[j][pl[2*w]] != S[i][pl[2*w+1]]:
                        tmpf = False
                        break
                if tmpf:
                    able[i] = False
                    able[j] = False
                    break
            else:
                if H % 2 == 0 or flag == 1:
                    flag = 2
                    break
                for w in range((W+1)//2):
                    if S[i][pl[2*w]] != S[i][pl[2*w+1]]:
                        flag = 2
                        break
                else:
                    flag = 1
                    able[i] = False
                if flag == 2:
                    break
                
    if flag != 2:
        print ("YES")
        break
else:
    print ("NO")

Submission status: Accepted

Solution code:
from collections import Counter
n,m = map(int,input().split())
grid = [list(input()) for i in range(n)]
def jc(a,b):
  l = len(a)
  used = [0]*l
  for i in range(l):
    if used[i]:
      continue
    for j in range(i+1,l):
      if used[j]:
        continue
      if a[i] == b[j] and b[i] == a[j]:
        used[i] = 1
        used[j] = 1
        break
  if used.count(0) <= l%2:
    return True
  else:
    return False
def judge(a):
  h = len(a)
  w = len(a[0])
  used = [0]*h
  for i in range(h):
    if used[i]:
      continue
    ci = Counter(a[i])
    for j in range(i+1,h):
      if used[j]:
        continue
      cj = Counter(a[j])
      if ci == cj:
        if jc(a[i],a[j]):
          used[i] = 1
          used[j] = 1
          break
  if used.count(0) <= h%2:
    return True
  else:
    return False
gt = list(zip(*grid))
if judge(grid) & judge(gt):
  print("YES")
else:
  print("NO")

Submission status: Accepted

Solution code:
def check(field):
    tr = list(map(''.join, zip(*field)))
    paired = set()
    center = -1
    for i, col1 in enumerate(tr):
        if i in paired:
            continue
        for j, col2 in enumerate(tr[i + 1:], start=i + 1):
            if j in paired:
                continue
            if col1 == col2[::-1]:
                paired.add(i)
                paired.add(j)
                break
        else:
            if center == -1 and col1 == col1[::-1]:
                center = i
            else:
                return False
    return True


def arrange_row(field, new_field, i, remain):
    if len(remain) == 0:
        return check(new_field)
    j = remain.pop()
    new_field[i] = field[j]
    for k in list(remain):
        remain.remove(k)
        new_field[h - i - 1] = field[k]
        result = arrange_row(field, new_field, i + 1, remain)
        if result:
            return True
        remain.add(k)
    remain.add(j)
    return False


def solve(h, w, field):
    new_field = [None] * h
    remaining_row = set(range(h))

    if h % 2 == 0:
        return arrange_row(field, new_field, 0, remaining_row)

    for i in list(remaining_row):
        remaining_row.remove(i)
        new_field[h // 2] = field[i]
        result = arrange_row(field, new_field, 0, remaining_row)
        if result:
            return True
        remaining_row.add(i)
    return False


h, w = map(int, input().split())
field = [input() for _ in range(h)]
print('YES' if solve(h, w, field) else 'NO')

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]


# ペアのとり方は 10395 通り
# a = math.factorial(12) / (2 ** 6) / math.factorial(6)
# print(a)  # 10395

def test(groups):
    seen = [False] * 6
    order = [-1] * len(groups)
    for i, g in enumerate(groups):
        if g == -1:
            # 真ん中
            order[W // 2] = i
            continue
        if not seen[g]:
            order[g] = i
            seen[g] = True
        else:
            order[~g] = i

    # print(groups, order)
    # return False

    rows = []
    for s in S:
        row = ''
        for i in order:
            row += s[i]
        rows.append(row)
    ok = [False] * H
    for i in range(H):
        if ok[i]:
            continue
        rev = rows[i][::-1]
        for j in range(i + 1, H):
            if not ok[j] and rows[j] == rev:
                ok[i] = ok[j] = True
                break
    ng_cnt = ok.count(False)
    if ng_cnt == 0:
        return True
    if ng_cnt == 1:
        i = ok.index(False)
        return rows[i] == rows[i][::-1]
    return False


def solve(groups, depth=0):
    if depth == W // 2:
        return test(groups)

    i = 0
    for _ in range(2 if W % 2 == 1 else 1):
        while groups[i] != -1:
            i += 1

        groups[i] = depth
        for j in range(i + 1, W):
            if groups[j] != -1:
                continue
            groups[j] = depth
            if solve(groups, depth + 1):
                return True
            groups[j] = -1
        groups[i] = -1
        i += 1

    return False


groups = [-1] * W
ok = solve(groups)
if ok:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
from random import randrange
readline = sys.stdin.readline

mod = 10**9+9
base = 2009   
def rollinhash(S):
    N = len(S)           
    has = 0
    for i in range(N):
        s = S[i]
        has = (has*base + s)%mod
    return has

phr = []
while len(set(phr)) != 26:
    phr = [randrange(1, 10**9) for _ in range(26)]
def shash(S):
    N = len(S)            
    has = 0
    for i in range(N):
        has = has + phr[S[i]]*phr[S[N-1-i]]
    return has

H, W = map(int, readline().split())
G = [list(map(ord, readline().strip())) for _ in range(H)]

ans = 'NO'
fh = H//2
ch = H-fh
lir = list(range(H))
seen = set()
for k in permutations(lir, ch):
    k = list(k)
    sk = set(k)
    for i in range(H):
        if i not in sk:
            k.append(i)
    
    sh = shash(k)
    if sh in seen:
        continue
    seen.add(sh)
    
    
    G2 = []
    for j in k:
        G2.append(G[j])
    G2 = list(map(list, zip(*G2)))
    G2h = [rollinhash(g) for g in G2]
    G2hi = [rollinhash(g[::-1]) for g in G2]
    
    used = [False]*W
    w1 = 0
    match = W//2
    while match and w1 < W:
        if used[w1]:
            w1 += 1
            continue
        sa = G2hi[w1]
        for w2 in range(w1+1, W):
            if used[w2]:
                continue
            if G2h[w2] == sa:
                used[w1] = True
                used[w2] = True
                match -= 1
                break
        w1 += 1
    if sum(used) >= W-1:
        if sum(used) == W-1:
            mid = used.index(False)
            if G2h[mid] == G2hi[mid]:
                ans = 'YES'
        else:
            ans = 'YES'
    if ans == 'YES':
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
import copy

sys.setrecursionlimit(10 ** 6)

def main():
    def per(s, a=[]):
        if not s:
            return [a]
        if len(s) % 2:
            cs = copy.deepcopy(s)
            res = []
            for u in cs:
                s.remove(u)
                res += per(s, [u] + a)
                s.add(u)
            return res
        u = min(s)
        s.remove(u)
        cs = copy.deepcopy(s)
        res = []
        for uu in cs:
            if uu < u: continue
            s.remove(uu)
            res += per(s, a + [u, uu])
            s.add(uu)
        s.add(u)
        return res

    ord_a = ord("a")
    h, w = map(int, input().split())
    t0 = [[ord(c) - ord_a for c in input()] for _ in range(h)]
    h_set = set(range(h))
    pattern = per(h_set)
    # print(t0)
    # print(pattern)
    b = h % 2
    for p in pattern:
        t1 = [[] for _ in range(h)]
        if b:
            t1[h // 2] = t0[p[0]]
        i = 0
        for ii in range(b, h, 2):
            t1[i] = t0[p[ii]]
            t1[h - 1 - i] = t0[p[ii + 1]]
            i += 1
        # print(p)
        # print(t1)
        fin = [False] * w
        mid = (w % 2 == 1)
        br = False
        for j, c0 in enumerate(zip(*t1)):
            if fin[j]: continue
            fin[j] = True
            c0 = c0[::-1]
            for jj, c1 in enumerate(zip(*t1)):
                if jj <= j: continue
                if fin[jj]: continue
                if c0 == c1:
                    fin[jj] = True
                    break
            else:
                if mid and c0 == c0[::-1]:
                    mid = False
                else:
                    br = True
                    break
        if br: continue
        print("YES")
        exit()
    print("NO")

main()

Submission status: Accepted

Solution code:
# この解法は嘘を含む

from itertools import groupby
H, W = map(int, input().split())
S_ = ["" for _ in range(W)]
T_ = []
for _ in range(H):
    s = input()
    T_.append(s)
    for i, c in enumerate(s):
        S_[i] += c
T = [sorted(t) for t in T_]
S = [sorted(s) for s in S_]
cnt = 0
for _, g in groupby(sorted(T)):
    if len(list(g))%2:
        cnt += 1
if H%2 < cnt:
    print("NO")
    exit()
cnt = 0
for _, g in groupby(sorted(S)):
    if len(list(g))%2:
        cnt += 1
if W%2 < cnt:
    print("NO")
    exit()
if W%2 or H%2:
    print("YES")
    exit()
T1 = []
T2 = []
for i, (_, t) in enumerate(sorted(zip(T, T_))):
    if i%2:
        T1.append(t)
    else:
        T2.append(t)
T_p = T1 + T2[::-1]
S_pp = ["" for _ in range(W)]
for t in T_p:
    for i, c in enumerate(t):
        S_pp[i] += c
S1 = []
S2 = []
for i, (_, s) in enumerate(sorted(zip(S, S_pp))):
    if i%2:
        S1.append(s)
    else:
        S2.append(s)
S_p = S1 + S2[::-1]
for s1, s2 in zip(S_p, S_p[::-1]):
    for c1, c2 in zip(s1, s2[::-1]):
        if c1!=c2:
            print("NO")
            exit()
print("YES")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import itertools
import numpy as np
from scipy.sparse.csgraph import connected_components

H,W = map(int,input().split())
words = np.array([list(input().rstrip()) for _ in range(H)], dtype='U1')

def gen_pair_pattern_even(rest):
    # 偶数個を仮定
    if len(rest) == 0:
        yield []
        return
    if len(rest) == 1:
        x = rest.pop()
        yield [(x,x)]
        return
    li = list(rest)
    x = li[0]
    for y in li[1:]:
        se = rest.copy()
        se.remove(x)
        se.remove(y)
        for p in gen_pair_pattern_even(se):
            yield p + [(x,y)]    

def gen_pair_pattern(N):
    if N & 1:
        for n in range(N):
            se = set(x for x in range(N) if x != n)
            for p in gen_pair_pattern_even(se):
                yield p + [(n,n)]
    else:
        for p in gen_pair_pattern_even(set(range(N))):
            yield p

def test(row_pairs):
    graph = np.ones((W,W), dtype = np.bool)
    for r1,r2 in row_pairs:
        graph &= (words[r1][:,None] == words[r2][None,:])
    graph &= graph.T
    se = set(range(W))
    while se:
        removed = False
        for i,j in itertools.combinations(se,2):
            if graph[i,j]:
                se.remove(i)
                se.remove(j)
                removed = True
                break
        if not removed:
            break
    if len(se) > 1:
        return False
    return True

bl = False
for p in gen_pair_pattern(H):
    if test(p):
        bl = True
        break

answer = 'YES' if bl else 'NO'
print(answer)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
G=[list(input()) for i in range(H)]
G_t=[list(x) for x in list(zip(*G))]
def Check(G,H,W):
  Paired_y=[False]*H
  for y1 in range(H):
    if Paired_y[y1]:
      continue
    for y2 in range(H):
      if y1==y2 or Paired_y[y2]:
        continue
      Paired_x=[False]*W
      for x1 in range(W):
        if Paired_x[x1]:
          continue
        for x2 in range(W):
          if x1==x2 or Paired_x[x2]:
            continue
          if G[y1][x1]==G[y2][x2] and G[y1][x2]==G[y2][x1]:
            Paired_x[x1]=True
            Paired_x[x2]=True
            break
      if W%2==1:
        if Paired_x.count(False)==1:
          r=Paired_x.index(False)
          if G[y1][r]==G[y2][r]:
            Paired_y[y1]=True
            Paired_y[y2]=True
            break
      else:
        if Paired_x.count(False)==0:
          Paired_y[y1]=True
          Paired_y[y2]=True
          break
  if H%2==1:
    if Paired_y.count(False)==1:
      return True
    else:
      return False
  else:
    if Paired_y.count(False)==0:
      return True
    else:
      return False
  
if Check(G,H,W) and Check(G_t,W,H):
  print("YES")
else:
  print("NO")

Submission status: Accepted

Solution code:
input = raw_input
range = xrange

n, m = map(int,input().split())
grid = [input() for i in range(n)]

use = [False]*n
cur = []
def backtrack_even(i, rem, addwhat):
    if rem == 0:
        if addwhat != None: cur.append(addwhat)
        check(cur)
        if addwhat != None: cur.pop()
        return
    if use[i]: return backtrack_even(i+1, rem, addwhat)
    use[i] = True; cur.append(i)
    for j in range(i+1, n):
        if use[j]: continue
        use[j] = True; cur.append(j)
        backtrack_even(i+1, rem-2, addwhat)
        use[j] = False; cur.pop()
    use[i] = False; cur.pop()

def backtrack():
    if n%2 == 0: return backtrack_even(0, n, None)
    for i in range(n):
        use[i] = True
        backtrack_even((0 if i else 1), n-1, i)
        use[i] = False

middle_initial = (m%2 == 0)
from collections import Counter
def check(cur):
    P = cur[::2] + cur[1::2][::-1]
    cols = Counter((''.join(grid[P[i]][j] for i in range(n))) for j in range(m))
    #print(cur, P, cols)
    middle_filled = middle_initial
    rem = m
    while rem:
        w = next(iter(cols))
        cols[w]-= 1; rem-= 1
        if cols[w] == 0: del cols[w]
        w2 = w[::-1]
        if w2 in cols:
            assert cols[w2]
            cols[w2]-= 1; rem-= 1
            if cols[w2] == 0: del cols[w2]
        elif w == w[::-1] and not middle_filled:
            middle_filled = True
        else: return False
    print("YES"); exit()

backtrack()
print("NO")

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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")