Problem:


Score : 1300 points

Problem Statement

There is a square-shaped grid with N vertical rows and N horizontal columns.
We will denote the square at the i-th row from the top and the j-th column from the left as (i,\ j).

Initially, each square is either white or black.
The initial color of the grid is given to you as characters a_{ij}, arranged in a square shape.
If the square (i,\ j) is white, a_{ij} is .. If it is black, a_{ij} is #.

You are developing a robot that repaints the grid.
It can repeatedly perform the following operation:

Select two integers i, j (1 ≤ i,\ j ≤ N). Memorize the colors of the squares (i,\ 1), (i,\ 2), ..., (i,\ N) as c_1, c_2, ..., c_N, respectively. Then, repaint the squares (1,\ j), (2,\ j), ..., (N,\ j) with the colors c_1, c_2, ..., c_N, respectively.

Your objective is to turn all the squares black.
Determine whether it is possible, and find the minimum necessary number of operations to achieve it if the answer is positive.

Constraints

2 ≤ N ≤ 500

a_{ij} is either . or #.

Partial Score

In a test set worth 300 points, N ≤ 3.

Input

The input is given from Standard Input in the following format:

N
a_{11}...a_{1N}
:
a_{N1}...a_{NN}

Output

If it is possible to turn all the squares black, print the minimum necessary number of operations to achieve the objective.
If it is impossible, print -1 instead.

Sample Input 1

2
#.
.#

Sample Output 1

3

For example, perform the operation as follows:

Select i = 1, j = 2.

Select i = 1, j = 1.

Select i = 1, j = 2.

The transition of the colors of the squares is shown in the figure below:

Sample Input 2

2
..
..

Sample Output 2

-1

Sample Input 3

2
##
##

Sample Output 3

0

Sample Input 4

3
.#.
###
.#.

Sample Output 4

2

Sample Input 5

3
...
.#.
...

Sample Output 5

5



Sample input:
2
#.
.#


Sample output:
3

Submission status: Accepted

Solution code:
N = int(input())
G = [[1 if s == '#' else 0 for s in input().strip()] for _ in range(N)]
Gm = list(map(sum, G))
GT = list(map(list, zip(*G)))
geta = sum(sum(g) == N for g in GT)
exist = [sum(g) > 0 for g in GT]
ans = -1
if sum(Gm) != 0:
    ans = N - geta + min(N - Gm[i] + 1 - exist[i] for i in range(N))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
nMAP = [["" for i in range(N)] for j in range(N)]
tMAP = [["" for i in range(N)] for j in range(N)]
c = 0
flag = 0
for i in range(N):
    s = list(str(input()))
    if "#" in s:
        flag = 1
    nMAP[i] = s
        
for i in range(N):
    for j in range(N):
        tMAP[i][j] = nMAP[j][i]
        
for i in range(N):
    if "." in tMAP[i]:
        c+=1
        
MIN = N
for i in range(N):
    x = nMAP[i].count(".")
    if "#" in tMAP[i]:
        MIN = min(MIN,x)
    else:
        MIN = min(MIN,x+1)
    
if flag == 0:
    print(-1)
else:
    print(MIN+c)

Submission status: Accepted

Solution code:
n,*a=open(0);n=int(n);*b,=zip(*a);f,e=[sum((c in t)^1for t in b)for c in'.#'];print(-(e>n)or min(n*2-f-x.count('#')+2-('#'in y)for x,y in zip(a,b)))

Submission status: Accepted

Solution code:
n,*a=open(0).readlines();n=int(n);*b,=zip(*a);f,e=[sum((c in t)^1for t in b)for c in'.#'];print(-(e>n)or min(n*2-f-x.count('#')+2-('#'in y)for x,y in zip(a,b)))

Submission status: Accepted

Solution code:
n,*a=open(0).readlines();n=int(n);*b,=zip(*a);f,e=[sum((c in t)^1for t in b)for c in'.#'];print(-(e>n)or min(n*2-f-a[i].count('#')+2-('#'in b[i])for i in range(n)))

Submission status: Accepted

Solution code:
n,*a=open(0).readlines();n=int(n);*b,=zip(*a);f,e=[sum((c in t)^1for t in b)-1for c in'.#'];print(-(e==n)or min(n*2-f-a[i].count('#')+(not'#'in b[i])for i in range(n)))

Submission status: Accepted

Solution code:
n,*a=open(0).readlines();n=int(n);*b,=zip(*a);f,e=[sum(n==t.count(c)for t in b)for c in'#.'];print(-(e==n)or min(n*2-f-a[i].count('#')+(not'#'in b[i])for i in range(n)))

Submission status: Accepted

Solution code:
s='#';n,*a=open(0).readlines();n=int(n);f=sum(n==t.count(s)for t in zip(*a));r=range(n);print(-all(not s in t for t in a)or min(n*2-f-a[i].count(s)+all(s<a[j][i]for j in r)for i in r))

Submission status: Accepted

Solution code:
n,*a=open(0).readlines();n=int(n);f,e=[sum(n==t.count(c)for t in zip(*a))for c in'#.'];r=range(n);print(-(e==n)or min(n*2-f-a[i].count('#')+all('#'<a[j][i]for j in r)for i in r))

Submission status: Accepted

Solution code:
s='#';n,*a=open(0).readlines();n=int(n);f,e=[sum(i==t.count(s)for t in zip(*a))for i in(n,0)];r=range(n);print(-(e>n)or min(n*2-f-a[i].count(s)+all(s<a[j][i]for j in r)for i in r))

Submission status: Accepted

Solution code:
s='#';n,*a=open(0).readlines();n=int(n);f=sum(n==t.count(s)for t in zip(*a));print(-all(t.count(s)<1for t in a)or min(n*2-f-a[i].count(s)+all(s<a[j][i]for j in range(n))for i in range(n)))

Submission status: Accepted

Solution code:
n=int(input());a=eval('list(input()),'*n);f=sum(n==t.count('#')for t in zip(*a));print(-all(t.count('#')<1for t in a)or min(n*2-f-a[i].count('#')+all(a[j][i]>'#'for j in range(n))for i in range(n)))

Submission status: Accepted

Solution code:
n=int(input());a=eval('list(input()),'*n);f=sum(n==t.count('#')for t in zip(*a));print(-all(t.count('#')<1for t in a)or min(n*2-f-b.count('#')+all(a[j][i]>'#'for j in range(n))for i,b in enumerate(a)))

Submission status: Accepted

Solution code:
n=int(input())
a=eval('list(input()),'*n)
if all(t.count('#')<1for t in a):
  print(-1)
  exit()
f=sum(n==t.count('#')for t in zip(*a))
c=10**18
for i,b in enumerate(a):
  v=b.count('#')
  t=0
  if b[i]!='#':
    for j in range(n):
      if a[j][i]=='#':
        break
    else:
      t+=1
    t+=n-v
  else:
    t+=n-v
  c=min(c,t+n-f)
print(c)

Submission status: Accepted

Solution code:
N=int(input())
Grid=[list(input()) for i in range(N)]
Grid_v=[list(x) for x in zip(*Grid)]
W,H=N,0
if Grid==[["."]*N for i in range(N)]:
  print(-1)
  exit()
for i in range(N):
  if Grid_v[i]!=["."]*N:
    W=min(W,N-Grid[i].count("#"))
  else:
    W=min(W,N-Grid[i].count("#")+1)
for i in range(N):
  if Grid_v[i]!=["#"]*N:
    H+=1
print(W+H)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = [[1 if c == '#' else 0 for c in S()] for _ in range(n)]
    b = [n-sum(a[i]) for i in range(n)]

    t = 0
    for i in range(n):
        if not all([a[j][i] == 1 for j in range(n)]):
            t += 1

    if min(b) == 0:
        return t

    if min(b) == n:
        return -1

    r = min(b) + 1 + t
    for i in range(n):
        ai = a[i]
        for j in range(n):
            if ai[j] == 0:
                continue
            if r > b[j] + t:
                r = b[j] + t

    return r


print(main())

Submission status: Accepted

Solution code:
from operator import itemgetter
n=int(input())
a=[list(map(lambda x:x=='#',input())) for i in range(n)]
cr,cc=list(map(sum,a)),[sum(map(itemgetter(i),a)) for i in range(n)]
mx=max(cr)
print(-1 if mx==0 else (not sum([cc[i] for i in range(n) if cr[i]==mx]))+n-mx+sum(map(lambda x:x<n,cc)))

Submission status: Accepted

Solution code:
N=int(input())
a=[input() for i in range(N)]
blackExistCol=[False for i in range(N)]
blackNumRow=[0 for i in range(N)]


flag=False
Max=-1
already=0

for i in range(N):
  for j in range(N):
    if a[i][j]=="#":
      blackExistCol[j]=True
      blackNumRow[i]+=1
      flag=True

if flag==False:
  print("-1")
else:
  for i in range(N):
    if blackExistCol[i]:
      if Max<blackNumRow[i]:
        Max=blackNumRow[i]
  Min=N-Max
  for j in range(N):
    for i in range(N):
      if a[i][j]==".":
        break
    else:
      already+=1
  temp=max(blackNumRow)
  Min2=N-temp+1
  
  ans=min(Min,Min2)+N-already
  
  print(ans)

Submission status: Accepted

Solution code:
def solve(n, a):
    if a == ['.'*n]*n:
        return -1
    white_column = sum(any(a[j][i] == '.' for j in range(n)) for i in range(n))
    res = float('inf')
    for r in range(n):
        all_white = all(a[i][r] == '.' for i in range(n))
        res = min(res, white_column + all_white + sum(1 for i in range(n) if a[r][i] == '.'))
    return res


n = int(input())
a = [input() for _ in range(n)]
print(solve(n, a))

Submission status: Accepted

Solution code:
n=int(raw_input())
a=[raw_input() for _ in xrange(n)]
cnt=0
for i in xrange(n):
    for j in xrange(n):
        if a[i][j]==".":
            cnt+=1
if cnt==n*n:
    print -1
    exit()

cnt=[0]*n
y=[False]*n
for i in xrange(n):
    for j in xrange(n):
        if a[i][j]==".":
            cnt[i]+=1
            y[i]=True
t=[False]*n
nokori=n
for j in xrange(n):
    tmp=0
    for i in xrange(n):
        if a[i][j]=="#":
            tmp+=1
    if tmp==n:
        nokori-=1
    if tmp!=0:
        t[j]=True

ans=9999999999
for i in xrange(n):
    if y[i]:
        if t[i]:
            ans=min(ans,cnt[i]+nokori)
        else:
            ans=min(ans,cnt[i]+nokori+1)
    else:
        ans=min(ans,nokori)
print ans

Submission status: Accepted

Solution code:
N = int(input().strip())
ar = [N*[] for _ in range(N)]
for row in range(N):
  ar[row] = input().strip()

fullestRows = []
maxCount = 0
for row in range(N):
  count = 0
  for col in range(N):
    if ar[row][col] == '#':
      count += 1
  if count > maxCount:
    maxCount = count
    fullestRows = [row]
  elif count == maxCount:
    fullestRows.append(row)

if maxCount == 0:
  print(-1)
else:
  found = False
  req = 0
  for fr in fullestRows:
    for row in range(N):
      if ar[row][fr] == '#':
        found = True
        break
    if found:
      break
  if not found:
    req += 1
  req += N - maxCount
  
  for col in range(N):
    for row in range(N):
      if ar[row][col] == '.':
        req+=1
        break
  print(req)

Submission status: Accepted

Solution code:
n = input()
A = [raw_input() for i in xrange(n)]

R = [sum(e[j] == '#' for j in xrange(n)) for e in A]
C = [sum(A[j][i] == '#' for j in xrange(n)) for i in xrange(n)]

c_need = sum(e < n for e in C)

INF = 10**9+7
ans = INF
for i in xrange(n):
    if R[i] == C[i] == 0:
        continue
    if C[i] == 0:
        ans = min(ans, n-R[i] + c_need + 1)
    else:
        ans = min(ans, n-R[i] + c_need)
print -1 if ans == INF else ans

Submission status: Accepted

Solution code:
N = int(input())
A = [[0 if x == "." else 1 for x in input()] for i in range(N)]

if sum([sum(x) for x in A]) == 0:
    print(-1)
else:
    sum_list = [0] * N
    for i in range(N):
        s = 0
        for j in range(N):
            s += A[j][i]
        sum_list[i] = s

    count = N + 1
    index = []
    for i in range(N):
        tmp = 0
        flag = False
        for j in range(N):
            if A[i][j] == 0:
                tmp += 1
            if sum_list[i] == 0:
                flag = True

        if flag:
            tmp += 1

        count = min(count, tmp)

        if count == 0:
            break

    for i in range(N):
        for j in range(N):
            if A[j][i] == 0:
                count += 1
                break

    print(count)

Submission status: Accepted

Solution code:
n = int(raw_input())
a = []

total = 0
for i in range(n):
    ai = raw_input()
    ai = map(lambda x: x == '#', ai)
    a.append(ai)
    total += sum(ai)

if total == 0:
    print -1
    exit()

b = [0] * n
for i in range(n):
    flag = 0
    for j in range(n):
        flag |= a[j][i]
    b[i] = flag^1

col = 0
for j in range(n):
    flag = 1
    for i in range(n):
        flag &= a[i][j]
    col += flag

ans = float('inf')
for i in range(n):
    total = 0
    flag = 0
    for j in range(n):
        if a[i][j] == 0:
            total += 1
            flag |= 1
    ans = min(ans, total + (flag&b[i]) + n-col)

print ans

Submission status: Accepted

Solution code:
N = int(raw_input())
A = [raw_input() for _ in xrange(N)]
counts = map(lambda x: x.count("#"), A)

if sum(counts) == 0:
	print -1
	exit(0)

for i in xrange(N):
	has_hash = False
	for j in xrange(N):
		if A[j][i] == "#":
			has_hash = True
	if not has_hash:
		counts[i] -= 1
ans = N+N-max(counts)

for j in xrange(N):
	complete = True
	for i in xrange(N):
		if A[i][j] != "#":
			complete = False
	if complete:
		ans -= 1

print ans

Submission status: Accepted

Solution code:
import sys                                                                      
                                                                                
grid = []                                                                       
                                                                                
N = int(raw_input())                                                            
                                                                                
for i in range(0,N):                                                            
    rowChars = list(raw_input())                                                
    rowNums = []                                                                
    for square in rowChars:                                                     
        if square == '.':                                                       
            rowNums.append(0)                                                   
        else:                                                                   
            rowNums.append(1)                                                   
    grid.append(rowNums)                                                        
                                                                                
                                                                                
# Check if totally blank (otherwise there exists a solution)                    
blackSquares = 0                                                                
for i in range(0,N):                                                            
    for j in range(0,N):                                                        
        blackSquares += grid[i][j]                                              
                                                                                
if blackSquares == 0:                                                           
    print "-1"                                                                  
    sys.exit()                                                                  
                                                                                
# Check for all black columns                                                   
colCounts = [0] * N                                                             
for i in range(0,N):                                                            
    for j in range(0,N):                                                        
        colCounts[j] += grid[i][j]                                              
                                                                                
allBlackColCount = 0                                                            
for i in range(0,N):                                                            
    if colCounts[i] == N:                                                       
        allBlackColCount += 1                                                   
                                                                                
# Check for any all black rows
allBlackRowCount = 0                                                            
for i in range(0,N):                                                            
    rowCount = 0                                                                
    for j in range(0,N):                                                        
        rowCount += grid[i][j]                                                  
                                                                                
    if rowCount == N:                                                           
        # Found all black row... we're done                                     
        print "%d" % (N - allBlackColCount)                                     
        sys.exit()                                                              
                                                                                
# No entirely black rows... What we'll do is for each row we will calculate the 
# cost of completing it and take the minimum.                                   
minCost = N                                                                     
for i in range(0,N):                                                            
    blackSquares = 0                                                            
    for j in range(0,N):                                                        
        blackSquares += grid[i][j]                                              
                                                                                
    whiteSquares = N - blackSquares                                             
                                                                                
    completionCost = 0                                                          
    # If the ith column has any black squares, we can use the corresponding row 
    # to fill in the holes in this row for a total number of moves equal to the 
    # number of white squares in the row                                        
    if colCounts[i] > 0:                                                        
        completionCost = whiteSquares                                           
    else:                                                                       
        completionCost = whiteSquares + 1                                       
                                                                                
    minCost = min(minCost, completionCost)                                      
                                                                                
print "%d" % (N - allBlackColCount + minCost)

Submission status: Accepted

Solution code:
from sys import stdin
rr = lambda: stdin.readline().strip()

N = int(rr())
A = []
for _ in xrange(N):
    A.append(map(lambda x: x=='#', rr()))

def solve(N, A):
    B = zip(*A)
    if not any(any(row) for row in A):
        return -1
    return len({c for c, col in enumerate(B)
                      if not all(col)}) +\
           min(N - sum(row) + (not any(B[r]))
               for r, row in enumerate(A))

print solve(N, A)

Submission status: Accepted

Solution code:
N = int(input())
a = [ [str=="#" for str in input()]for _ in range(N)]
#all_source = [(i,j) for j in range(N) for i in range(N)]

n =0
ans =9999999999999
all_black_row = sum(all(a[i][j] for i in range(N)) for j in range(N))
black_count_line  = [(sum(a[i][j] for j in range(N))) for i in range(N)]
black_count_row = [(sum(a[i][j] for i in range(N))) for j in range(N)]
for line_no,blacks in enumerate(black_count_line):
    tmp_ans = N -  all_black_row
    if black_count_row[line_no] ==0:
        tmp_ans +=1
    tmp_ans += N-blacks
    ans = min(ans,tmp_ans)

if not any(black_count_line) and not any(black_count_row):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    A = [[0 if j == '.' else 1 for j in input()] for i in range(N)]
    ans = 0
    min_r = float('inf')
    num_f = 0

    check = 0
    for i in range(N):
        check += sum(A[i])
    if check == 0:
        print(-1)
        return None

    for j in range(N):
        for i in range(N):
            if not A[i][j]:
                break
        else:
            num_f += 1

    if num_f == N:
        print(0)
        return None

    exits = [False] * N
    for j in range(N):
        for i in range(N):
            if A[i][j]:
                exits[j] = True
                break

    # min_r search
    for i in range(N):
        tmp = 0
        tmp += (not exits[i])

        for j in range(N):
            if A[i][j] == 0:
                tmp += 1

        min_r = min(tmp, min_r)

    ans = (N - num_f) + min_r
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from operator import itemgetter
n = int(input())
data = [list(map(lambda x: x == '#', input().strip())) for i in range(n)]
row_cnt = list(map(sum, data))
col_cnt = [sum(map(itemgetter(i), data)) for i in range(n)]

mr = max(row_cnt)
if not mr:
  print(-1)
else:
  temp = sum([col_cnt[i] for i in range(n) if row_cnt[i] == mr])
  k0 = 0 if temp else 1
  k1 = n - mr
  k2 = sum(map(lambda x: x < n, col_cnt))
  print(k0+k1+k2)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[list(input()) for i in range(n)]
if max([a[i].count("#") for i in range(n)]) ==0:
  print(-1)
  exit()
minus=0
for i in range(n):
  if a[i].count(".")==0:
    minus=n
    break
  if a[i][i]=="#":
    minus=max(minus,a[i].count("#"))
b=zip(*a)
for j in range(n):
  if b[j].count(".")==0:
    minus+=1
print(2*n-minus)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[list(input()) for i in range(n)]
if max(a[i].count("#") for i in range(n)) ==0:
  print(-1)
  exit()
minus=0
for i in range(n):
  if a[i].count(".")==0:
    minus=n
    break
  if a[i][i]=="#":
    minus=max(minus,a[i].count("#"))
b=zip(*a)
for j in range(n):
  if b[j].count(".")==0:
    minus+=1
print(2*n-minus)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
if max(a[i].count(".") for i in range(n)) ==0:
  print(-1)
  exit()
minus=0
for i in range(n):
  if a[i].count(".")==0:
    minus=n
    break
  elif a[i][i]=="#":
    minus=max(minus,a[i].count("#"))
b=zip(*a)
for j in range(n):
  if b[j].count(".")==0:
    minus+=1
print(2*n-minus)

Submission status: Runtime Error

Solution code:
N = int(input().strip())
ar = [N*[] for _ in range(N)]
for row in range(N):
  ar[row] = input().strip()

count = N*[0]
fullestRow = -1
maxCount = 0
for row in range(N):
  for col in range(N):
    if ar[row][col] == '#':
      count[row] += 1
  if count[row] > maxCount:
    maxCount = count[row]
    fullestRow = row

if maxCount == 0:
  print(-1)
else:
  req = 0
  for row in range(N):
    if ar[row][fullestRow] == '#':
      found = True
      break
  if not found:
    req += 1
  req += N - maxCount
  
  for col in range(N):
    for row in range(N):
      if ar[row][col] == '.':
        req+=1
        break
  print(req)

Submission status: Runtime Error

Solution code:
N = int(input().strip())
ar = [N*[] for _ in range(N)]
for row in range(N):
  ar[row] = list(input().strip())

count = N*[0]
missing = [N*[] for _ in range(N)]
fullestRow = -1
maxCount = 0
for row in range(N):
  for col in range(N):
    if ar[row][col] == '#':
      count[row] += 1
    else:
      missing[row].append(col)
  if count[row] > maxCount:
    maxCount = count[row]
    fullestRow = row

if maxCount == 0:
  print(-1)
else:
  req = 0
  for row in range(N):
    if ar[row][fullestRow] == '#':
      found = True
      break
  if not found:
    req += 1
  req += N - maxCount
  
  for col in range(N):
    for row in range(N):
      if ar[row][col] == '.':
        req+=1
        break
  print(req)

Submission status: Runtime Error

Solution code:
from collections import deque


def count(board: list):
    ret = 0
    for row in board:
        for cell in row:
            if cell == '#':
                ret += 1
    return ret


N = int(input())
A = []
d = {}

if n > 3 : exit()

for i in range(N):
    A.append(input())

if count(A) == 0:
    print(-1)
    exit()

que = deque()
que.append((0, A))
d["".join(A)] = 0

while len(que) > 0:
    t,b = que[0]
    que.popleft()

    # print(t,b)
    if (count(b) == N * N):
        print(t)
        exit()

    for i in range(N):
        for j in range(N):
            new_b = [list(r) for r in b]
            for k in range(N):
                new_b[k][j] = b[i][k]
            new_b = ["".join(r) for r in new_b]

            if "".join(new_b) in d:
                continue
            else:
                # 適当な値でメモ
                d["".join(new_b)] = True
                que.append((t + 1, new_b))

Submission status: Runtime Error

Solution code:
import numpy as np

def change(a, i, j):
    b = np.copy(a)
    b[:,j] = b[i,:]
    return b

def isTrue(maxiter, current, a):
    n = a.shape[0]
    if np.all(a):
        return current
    current += 1
    ret = maxiter+1
    if maxiter < current:
        return ret
    for i in range(n):
        for j in range(n):
            b = change(a,i,j)
            if np.all(a==b):
                ret = min(ret,maxiter)
            else:
                ret = min(ret,isTrue(maxiter, current, b))
            
    return ret
                
            
n = int(input())
a = []
for _ in range(n):
    a.append([num=='#' for num in input().split(' ')])
a = np.array(a)

ret = isTrue(n*2,0,a)
if ret > n*2:
    ret = -1
print(ret)

Submission status: Runtime Error

Solution code:
from collections import deque
n = input()
A = ''.join(raw_input() for i in xrange(n))

if n > 5:
    exit(1)

ALL = "#"*(n*n)

deq = deque()

deq.append((A, 0))
memo = {}
while deq:
    state, cost = deq.popleft()
    if state == ALL:
        print cost
        break
    if state in memo:
        continue
    s = list(state)
    memo[state] = 1
    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]
            deq.append((''.join(n_state), cost+1))
else:
    print -1

Submission status: Runtime Error

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict, deque
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

N = read()
L = N * N

assert(N <= 3)

a = ""
for _ in range(N):
  a += input()

queue = deque()
queue.append((a, 0))
visited = set()
visited.add(a)

while len(queue) != 0:
  (a, k) = queue.popleft()
  if a == "#" * L:
    print(k); exit()
  for i, j in product(range(N), range(N)):
    b = list(a)
    b[j:L:N] = b[N*i:N*(i+1)]
    b = "".join(b)
    if not b in visited:
      visited.add(b)
      queue.append((b, k+1))

print("-1")

Submission status: Runtime Error

Solution code:
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]
            if ''.join(n_state) == state:
                continue
            res = min(res, dfs(''.join(n_state))+1)
    memo[state] = res
    return res
ans = dfs(A)
if ans > 10**5:
    print -1
else:
    print ans

Submission status: Runtime Error

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