Submission #1131175

---

Source Code Expand

n = input()
A = ''.join(raw_input() for i in xrange(n))

if n > 5:
    exit(1)

ALL = "#"*(n*n)

memo = {}
def dfs(state):
    if state in memo:
        return memo[state]
    if state == ALL:
        return 0
    s = list(state)
    memo[state] = res = 10**9
    for i in xrange(n):
        C = [state[i*n+k] for k in xrange(n)]
        for j in xrange(n):
            n_state = s[:]
            for k in xrange(n):
                n_state[k*n+j] = C[k]
            res = min(res, dfs(''.join(n_state))+1)
    memo[state] = res
    return res
ans = dfs(A)
if ans == 10**9:
    print -1
else:
    print ans

Submission Info

Judge Result