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: Wrong Answer

Solution code:
# coding: utf-8
import sys

n = int(input())
field = [None] * n
for i in range(n):
    field[i] = [c == '#' for c in input().strip()]


def sort_row(field):
    return sorted(range(n), key=lambda i: -sum(field[i]))


def find_bk_col(field, row):
    for r in range(n):
        if field[r][row]:
            return r
    return None


def cnt_all_bk_col(field):
    cnt = 0
    for c in range(n):
        if all([field[r][c] for r in range(n)]):
            cnt += 1
    return cnt


def main():
    row_list = sort_row(field)
    for r in row_list:
        sys.stderr.write("row %d:\n" % r)
        if sum(field[r]) == 0:
            break
        bc = find_bk_col(field, r)
        sys.stderr.write(str(bc) + "\n")
        if bc is not None:
            cnt = n - sum(field[r])
            cnt += n - cnt_all_bk_col(field)
            return cnt
    if sum(field[row_list[0]]) > 0:
        return n * 2
    return -1


print(main())

Submission status: Wrong Answer

Solution code:
from itertools import product as prod

n = int(input())
als = [list(input()) for _ in range(n)]

def transpose_matrix(mat):
    newmat = [["@"] * n for _ in range(n)]
    for i, j in prod(range(n), repeat=2):
        newmat[i][j] = mat[i][j]
    return newmat

def count_black_dot(als):
    rowcnts = []
    colcnts = []
    for al in als:
        rowcnts.append(al.count("#"))

    t_als = transpose_matrix(als)
    for t_al in als:
        colcnts.append(t_al.count("#"))

    return rowcnts, colcnts

ans = 0
maxcnt = float("inf")
rowcnts, colcnts = count_black_dot(als)
row_line, col_line = rowcnts.count(n), colcnts.count(n)
row_max, col_max = max(rowcnts), max(colcnts)

if row_max == 0:
    ans = -1
elif row_line != 0:
    ans = n - col_line
else:
    ans += n - row_max
    ans += n - col_line

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
n = int(input())
a = [[0]*n]*n
check = ['#']*n
check2 = ['.']*n

def rep(i,j):
    c = ['']*n
    for k in range(n):
        c[k] = a[i][k]
    for k in range(n):
        a[k][j] = c[k]
    return 0

for i in range(n):
    tmp = input()
    a[i] = list(tmp)

flag = 0
flag2 = 0
for i in range(n):
    if a[i] != check:
        flag = 1
        break
for i in range(n):
    if a[i] != check2:
        flag2 = 1
        break

if flag == 0:
    print(0)
elif flag2 != 1:
    print(-1)
else:
    m = 0
    c = []
    tmpi = 0
    for i in range(n):
        if m <= a[i].count('#'):
            m = a[i].count('#')
            tmpi = i
    for i in range(n):
        flag = 0
        for j in range(n):
            if a[j][i] != '#':
                flag = 1
                break
        if flag == 0:
            c.append(i)
    if m == n:                
        print(m-len(c))
        
    else:
        #print(tmpi,m)
        ad = n-m
        print(ad + n - len(c))

Submission status: Wrong Answer

Solution code:
import numpy    
if __name__ == '__main__':
    pass

Submission status: Wrong Answer

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

    # min_r search
    for i in range(N):
        tmp = 0

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

        min_r = min(tmp, min_r)

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

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

if sum(map(lambda x: x[0], counts)) == 0:
	print -1
	exit(0)

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

max_count = max(counts, key=lambda x: x[0] if x[1] else 0)[0]

print N+N-max_count-complete_cols

Submission status: Wrong Answer

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+1)
            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()])
a = np.array(a)

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

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
n = int(input())
a = [[0]*n]*n
check = ['#']*n
check2 = ['.']*n

def rep(i,j):
    c = ['']*n
    for k in range(n):
        c[k] = a[i][k]
    for k in range(n):
        a[k][j] = c[k]
    return 0

for i in range(n):
    tmp = input()
    a[i] = list(tmp)

flag = 0
flag2 = 0
for i in range(n):
    if a[i] != check:
        flag = 1
        break
for i in range(n):
    if a[i] != check2:
        flag2 = 1
        break

if flag == 0:
    print(0)
elif flag2 != 1:
    print(-1)
else:
    m = 0
    c = []
    tmpi = 0
    for i in range(n):
        if m <= a[i].count('#'):
            m = a[i].count('#')
            tmpi = i
    for i in range(n):
        flag = 0
        for j in range(n):
            if a[j][i] != '#':
                flag = 1
                break
        if flag == 0:
            c.append(i)
    if m == n:
        print(m-len(c))
        
    else:
        #print(tmpi,m)
        ad = n-m
        print(ad + n)

Submission status: Wrong Answer

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)]

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

Submission status: Wrong Answer

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)
    #Every row with white must get painted
    cand_rows = {r for r, row in enumerate(A)
                 if any(not x for x in row) }

    #If there's a black col, then done
    if any( all(col) for col in B ):
        return len(cand_rows)

    #Suppose column j is going to get repaired
    # to be all black.  It depends on the values of
    #  A[j][j2] for choice of j2.  If any are black,
    # we can repair it.
    INF = 1e9
    best = INF
    for cand_j in xrange(N):
        cand = set(cand_rows)
        to_fix = {i for i,x in enumerate(B[cand_j]) if not x}
        #naive
        if any(A[cand_j]):
            best = min(best, len(to_fix) + len(to_fix | cand))
        
            
    return best if best < INF else -1

print solve(N, A)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
 

def change(a,i,j,n):
    b = a
    imask = (2**n-1) << i*n
    jmask = 0
    for k in range(n):
        jmask |= (1<<k*n+n-1-j)
    buf = (a & imask) >> i*n
    chg = 0
    for k in range(n)[::-1]:
        #print(bin(((buf&(1<<k))>>k)))
        #print(bin(((buf&(1<<k))>>k)<<k*n+n-1-j))
        chg |= (((buf&(1<<k))>>k)<<k*n+n-1-j)
    b = (b-(b&jmask)+chg)
    return b
                
          
n = int(input())
a = ''
for i in range(n):
    a += input()
a = a.replace('#','1')
a = a.replace('.','0')
a = '0b'+a
a = int(a, 2)
#print(a)

#n = 3
max = 2**(n**2)
#a = 0b000010000

dp = [2*n+1 for _ in range(max)]
dp[a] = 0
for _ in range(2*n-1):
    for dpi in range(max):
        for i in range(n):
            for j in range(n):
                b = change(dpi,i,j,n)
                dp[b] = min(dp[dpi]+1,dp[b])
if dp[-1] > 2*n:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

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 = {}

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

Solution code:
import numpy as np
 

def change(a,i,j,n):
    b = a
    imask = (2**n-1) << i*n
    jmask = 0
    for k in range(n):
        jmask |= (1<<k*n+n-1-j)
    buf = (a & imask) >> i*n
    chg = 0
    for k in range(n)[::-1]:
        #print(bin(((buf&(1<<k))>>k)))
        #print(bin(((buf&(1<<k))>>k)<<k*n+n-1-j))
        chg |= (((buf&(1<<k))>>k)<<k*n+n-1-j)
    b = (b-(b&jmask)+chg)
    return b
                
          
n = int(input())
a = ''
for i in range(n):
    a += input()
a = a.replace('#','1')
a = a.replace('.','0')
a = '0b'+a
a = int(a, 2)
#print(a)

#n = 3
max = 2**(n**2)
#a = 0b000010000

dp = [2*n+1 for _ in range(max)]
dp[a] = 0
for _ in range(2*n):
    for dpi in range(max):
        for i in range(n):
            for j in range(n):
                b = change(dpi,i,j,n)
                dp[b] = min(dp[dpi]+1,dp[b])
if dp[-1] > 2*n:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
import numpy as np

n=int(input())
l=[]
for i in range(n):
	l.append(list(input()))

for i in range(n):
	for j in range(n):
		if l[i][j] == ".":
			l[i][j] = 0
		else:
			l[i][j] = 1

l=np.array(l)

# n=3
# l=np.array([[0,0,0],[0,1,0],[0,0,1]])

if all([l[x][y]==0 for x in range(n) for y in range(n)]):
	print(-1)
	exit()

q = Queue()

q.put([l,0])

while not q.empty():
	t = q.get()
	flag = True
	for i in range(n):
		for j in range(n):
			if t[0][i][j] == 0:
				flag = False
				break
		if flag == False:
			break
	if flag:
		res = t[1]
		break
	for i in range(n):
		if any([x==1 for x in t[0][i,:]]):
			for j in range(n):		
				tmp = np.array(t[0])
				tmp[:,j] = np.array(tmp[i,:])
				q.put([tmp,t[1]+1])

print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
def change(a, i, j):
    b = np.copy(a)
    b[:,j] = a[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) or np.all(b==False):
                ret = min(ret,maxiter+1)
            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()])
a = np.array(a)
 
ret = isTrue(n*2,0,a)
if ret > n*2:
    ret = -1
print(ret)

Submission status: Time Limit Exceeded

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

def f(i_,j_,A):
    global n
    n+=1
    A_copy =   [[ A[i][j] for j in range(N)]for i in range(N)]
    for i,val in enumerate([A[i_][j] for j in range(N) ]):
        A_copy[i][j_] =val
    return A_copy


def slow_solve(n,a):
    if n>5:
        return 99999
    if all(a[i][j]==True for i,j in all_source):
        return n
    min_val = 999999
    for i,j in all_source:
        a_copy = f(i,j,a)
        min_val = min(min_val,slow_solve(n+1,a_copy))
    return min_val


ans = (slow_solve(0,a))
if ans >100:
    ans = 6
if not any(a[i][j]==True for i,j in all_source):
    ans  = -1
print(ans)

Submission status: Time Limit Exceeded

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

def f(i_,j_,A):
    global n
    n+=1
    A_copy =   [[ A[i][j] for j in range(N)]for i in range(N)]
    for i,val in enumerate([A[i_][j] for j in range(N) ]):
        A_copy[i][j_] =val
    return A_copy


def slow_solve(n,a):
    if n>5:
        return 99999
    if all(a[i][j]==True for i,j in all_source):
        return n
    min_val = 999999
    for i,j in all_source:
        a_copy = f(i,j,a)
        min_val = min(min_val,slow_solve(n+1,a_copy))
    return min_val


ans = (slow_solve(0,a))
if ans >100:
    ans = 6
if not any(a[i][j]==True for i,j in all_source):
    ans  = -1
print(ans)
#print(n)
"""


a =f(2,1,a)
a =f(2,0,a)
a =f(2,0,a)
a =f(2,1,a)
a =f(2,2,a)
print(a)

3
...
...
..#
"""

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools


def nicos(N):
    nico_canidate = []
    seed = "25"
    nowstr = seed
    while (int(nowstr) <= N):
        nico_canidate.append(int(nowstr))
        nowstr += seed
    return nico_canidate


N = int(sys.stdin.readline().rstrip())

initialgamemap = [
    [0 if item == "#" else 1 for item in sys.stdin.readline().rstrip()] for _ in range(N)
    ]


#
# def sumrow(gamemap, i):
#     return sum(gamemap[i])
#
#
# def sumcolumn(gamemap, i):
#     return sum(line[i] for line in gamemap)
#
#
def sumtotal(gamemap):
    return sum(sum(line) for line in gamemap)


#
# for i in range(N):
#     if (sumrow(initialgamemap, i) == N and sumcolumn(initialgamemap, i) == N):
#         print(-1)
#         exit(0)
if sumtotal(initialgamemap) == N * N:
    print(-1)
    exit(0)


def gethash(gamemap):
    val = 0
    rad = 0
    for line in gamemap:
        for item in line:
            rad += 1
            val += (item << rad)
    return val


memo = set()
queue = [(initialgamemap, 0)]
while True:
    gamemap, count = queue.pop(0)
    if sumtotal(gamemap) == 0:
        print(count)
        exit(0)
    for i, j in itertools.product(range(N), repeat=2):
        copiedgamemap = [[item for item in line] for line in gamemap]
        for x in range(N):
            copiedgamemap[x][j] = gamemap[i][x]
        gamehash = gethash(copiedgamemap)
        if not gamehash in memo:
            memo.add(gamehash)
            queue.append((copiedgamemap, count + 1))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools


def nicos(N):
    nico_canidate = []
    seed = "25"
    nowstr = seed
    while (int(nowstr) <= N):
        nico_canidate.append(int(nowstr))
        nowstr += seed
    return nico_canidate


N = int(sys.stdin.readline().rstrip())

initialgamemap = [
    [0 if item == "#" else 1 for item in sys.stdin.readline().rstrip()] for _ in range(N)
    ]


#
# def sumrow(gamemap, i):
#     return sum(gamemap[i])
#
#
# def sumcolumn(gamemap, i):
#     return sum(line[i] for line in gamemap)
#
#
def sumtotal(gamemap):
    return sum(sum(line) for line in gamemap)


#
# for i in range(N):
#     if (sumrow(initialgamemap, i) == N and sumcolumn(initialgamemap, i) == N):
#         print(-1)
#         exit(0)
if sumtotal(initialgamemap) == N * N:
    print(-1)
    exit(0)

queue = [(initialgamemap, 0)]
while True:
    gamemap, count = queue.pop(0)
    if sumtotal(gamemap) == 0:
        print(count)
        exit(0)
    for i, j in itertools.product(range(N), repeat=2):
        copiedgamemap = [[item for item in line] for line in gamemap]
        for x in range(N):
            copiedgamemap[x][j] = gamemap[i][x]
        queue.append((copiedgamemap, count + 1))

Submission status: Accepted

Solution code:
n = int(input())
a = [list(input()) for i in range(n)]
cntr, cntc = [i.count(".") for i in a], [i.count(".") for i in zip(*a)]
if sum(cntr) == 0:
    exit(print(0))
if sum(cntr) == n * n:
    exit(print(-1))
if any(i == 0 for i in cntr):
    cnt = 0
    for i in cntc:
        cnt += 1 if i > 0 else 0
    exit(print(cnt))
cnt2 = 0
ans = float("inf")
for i in cntc:
    cnt2 += 1 if i > 0 else 0
for i in range(n):
    ans = min(ans, cntr[i] + cnt2 + 1) if cntc[i] == n else min(ans, cntr[i] + cnt2)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
a = [list(input().rstrip()) for _ in range(N)]

ans = float('inf')
b = 0
for j in range(N):
    if any(a[i][j] == '.' for i in range(N)):
        b += 1
for i in range(N):
    if any(a[k][i] == '#' for k in range(N)):
        ans = min(ans, a[i].count('.') + b)
    elif any(a[i][k] == '#' for k in range(N)):
        ans = min(ans, a[i].count('.') + b + 1)
print(ans if ans < float('inf') else -1)

Submission status: Accepted

Solution code:
n = int(input())
s = [input() for i in range(n)]


sharp_cnt = 0
for i in range(n):
    sharp_cnt += s[i].count("#")
if sharp_cnt == 0:
    print(-1)
    exit()

ans = n
for j in range(n):
    tate_all_sharp = all([s[i][j] == "#" for i in range(n)])
    if tate_all_sharp:
        ans -= 1

# 横一列#をつくる
need_cnt = n
for j in range(n):
    tate_any_sharp = any([s[i][j] == "#" for i in range(n)])
    if not tate_any_sharp:
        continue
    tmp = 0
    for i in range(n):
        if s[j][i] == ".":
            tmp += 1
    need_cnt = min(tmp, need_cnt)
    
for i in range(n):
    tmp = 0
    for j in range(n):
        if s[i][j] == ".":
            tmp += 1
    need_cnt = min(tmp + 1, need_cnt)

ans += need_cnt
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [input() for _ in range(n)]

cnt_col = [0]*n
cnt_row = [0]*n

for i in range(n):
    for j in range(n):
        if(a[i][j] == '#'):
            cnt_col[i] += 1
            cnt_row[j] += 1

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

b_row = cnt_row.count(n)


ans = 2*n
for i in range(n):
    if(cnt_col[i] == n):
        ans = min(ans, n-b_row)
        continue

    if(cnt_row[i] > 0):
        ans = min(ans, n-cnt_col[i] + n-b_row)
    else:
        ans = min(ans, n-cnt_col[i] + n-b_row + 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
a = [input()[:-1] for _ in range(N)]
row_white = [0]*N
col_white = [0]*N

for i in range(N):
    for j in range(N):
        if a[i][j]=='.':
            row_white[i] += 1

for i in range(N):
    for j in range(N):
        if a[j][i]=='.':
            col_white[i] += 1

if row_white==[N]*N:
    print(-1)
    exit()

ans = 10**18
C = 0

for i in range(N):
    if col_white[i]>0:
        C += 1

for i in range(N):
    if col_white[i]<N:
        ans = min(ans, row_white[i]+C)
    else:
        ans = min(ans, row_white[i]+1+C)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a=["" for i in range(N)]
data=[0]*N
for i in range(N):
    a[i]=input()
    data[i]=a[i].count("#")

if sum(data)==0:
    print(-1)
elif sum(data)==N**2:
    print(0)
else:
    data2=[0 for i in range(N)]
    for i in range(N):
        for j in range(N):
            data2[j]+=(a[i][j]=="#")
    count=0
    for i in range(N):
        if data2[i]!=N:
            count+=1
    ans=10**10
    for i in range(N):
        test=(N-data[i])+count+(data2[i]==0)
        ans=min(ans,test)

    print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    grid = [input() for _ in [0]*n]
    for i in grid:
        if "#" in i:
            break
    else:
        print(-1)
        return
    ans = 10**20
    # i行目に何個黒があるか
    black_cnt = [0]*n
    # i列目に黒が一つでもあればTrue
    exist = [False]*n
    for i in range(n):
        for j in range(n):
            if grid[i][j] == "#":
                black_cnt[i] += 1
                exist[j] = True
    # 縦一列が既に黒の列の数
    all_cnt = 0
    for j in range(n):
        for i in range(n):
            if grid[i][j] == ".":
                break
        else:
            all_cnt += 1
    for i in range(n):
        if exist[i]:
            ans = min(ans, n-black_cnt[i]+n-all_cnt)
        else:
            ans = min(ans, 2*n-black_cnt[i]-all_cnt+1)
    print(ans)


main()

Submission status: Accepted

Solution code:
N = int(input())
X = [[1 if a == "#" else 0 for a in input()] for _ in range(N)]
C = [sum([X[i][j] for i in range(N)]) for j in range(N)]
a = N - max(sum(X[i]) - (0 if C[i] else 1) for i in range(N))
b = N - C.count(N)
print(-1 if sum(C) == 0 else a + b)

Submission status: Accepted

Solution code:
N = int(input())
A = [input() for i in range(N)]
row_w = [row.count('.') for row in A]
col_w = [col.count('.') for col in zip(*A)]

if all(w==0 for w in row_w):
    print(0)
    exit()
if all(w==N for w in row_w):
    print(-1)
    exit()
if any(w==0 for w in row_w):
    print(len([1 for w in col_w if w>0]))
    exit()

ng_col = len([1 for w in col_w if w>0])
ans = 10**10
for i,rw in enumerate(row_w):
    tmp = rw + (col_w[i]==N) + ng_col
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
a = [input() for _ in range(n)]

min1 = 1000000
all_white = True
all_black = False
row_exist = [False for _ in range(n)]
row_white = [0 for _ in range(n)]

for i in range(n):
	cnt = 0
	for j in range(n):
		if a[i][j] == "#":
			cnt += 1
			row_exist[j] = True
	if cnt > 0:
		all_white = False
	if cnt == n:
		all_black = True
	row_white[i] = n - cnt

if all_white:
	print(-1)
	sys.exit()
if all_black:
	cnt = 0
	for i in range(n):
		for j in range(n):
			if a[j][i] == ".":
				cnt += 1
				break
	print(cnt)
else:
	ans = 0
	first_min = n
	for i in range(n):
		if row_exist[i]:
			first_min = min(first_min, row_white[i])
		else:
			first_min = min(first_min, row_white[i] + 1)
	ans += first_min
	cnt = 0
	for i in range(n):
		for j in range(n):
			if a[j][i] == ".":
				cnt += 1
				break
	ans += cnt
	print(ans)

Submission status: Accepted

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
b=list(zip(*a))
for i in range(n):
  if b[i].count("#")>=1:
    minus=max(minus,a[i].count("#"))
  else:
    minus=max(minus,a[i].count("#")-1)
for j in range(n):
  if b[j].count(".")==0:
    minus+=1
print(2*n-minus)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
state = [list(input().rstrip()) for _ in range(N)]

ColState = [0]*N
fullcols = 0
for w in range(N):
    isfull = True
    isempty = True
    for h in range(N):
        if state[h][w] == "#":
            isempty = False
        else:
            isfull = False
    if isfull:
        fullcols += 1
    if isempty:
        ColState[w] = -1

ans = 10**14
for h in range(N):
    emp = 0
    for w in range(N):
        if state[h][w] == ".":
            emp += 1
    if ColState[h] == -1:
        emp += 1
    ans = min(ans, emp+(N-fullcols))

if ans == 2*N+1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

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


N = int(sys.stdin.buffer.readline())
A = [list(sys.stdin.buffer.readline().decode().rstrip()) for _ in range(N)]
A = np.array(A, dtype='U1')

col_has_black = np.any(A == '#', axis=0)
row_has_black = np.any(A == '#', axis=1)
col_all_black = np.all(A == '#', axis=0)
row_all_black = np.all(A == '#', axis=1)

# 黒がなかったら作れない
if np.all(~col_has_black):
    print(-1)
    exit()


def count_row_to_black(i):
    # 黒にする行を決めたときに何手で真っ黒にできるか
    whites = np.count_nonzero(A[i] == '.')
    # 最低でも白の数だけは手数が必要
    if col_has_black[i]:
        # 対応する列に黒があれば、その行を使って i 行目を黒くする
        return whites
    else:
        # どっかから対応する列に黒を持ってきて↑やる
        return whites + 1


# 全部黒の行を1つ以上作らないといけない
ans = INF
for i in range(N):
    cnt = count_row_to_black(i) + (N - col_all_black.sum())
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ii,jj=[0]*n,[0]*n
b=0
for i in range(n):
  s=input()
  for j in range(n):
    k=1if"#"==s[j] else 0
    ii[i]+=k
    jj[j]+=k
    b+=k
if b==0:print(-1);exit()
c=n-jj.count(n)
mi=10000
for i in range(n):
  x=n-ii[i]
  if jj[i]==0:x+=1
  mi=min(x,mi)
print(mi+c)

Submission status: Accepted

Solution code:
import sys

N = int(input())

a = []

ybl = 0
tbl = 0

for i in range(N):

    A = list(input())

    if "." not in A:
        ybl += 1

    a.append(A)


blexist = False
for j in range(N):

    blnum = 0

    for i in range(N):

        if a[i][j] == "#":
            blexist = True
            blnum += 1

    if blnum == N:
        tbl += 1

#print (blexist,tbl,ybl)

if not blexist:
    print (-1)
    sys.exit()

if ybl != 0:
    print (N - tbl)
    sys.exit()


ans = float("inf")

for i in range(N):

    bexi = False
    for j in range(N):
        if a[j][i] == "#":
            bexi = True
            break

    

    chnum = 0
    for j in range(N):
        if a[i][j] == ".":
             chnum += 1

    if bexi:
        ans = min(ans,chnum + (N - tbl))

    else:
        ans = min(ans,chnum + 1 + (N - tbl))

        

print (ans)

Submission status: Accepted

Solution code:
N = int(input())
grid = []
for _ in range(N):
    grid.append(input())

col_info = [0] * N
for j in range(N):
    cnt = 0
    for i in range(N):
        if grid[i][j] == '#':
            cnt += 1
        else:
            cnt -= 1
    if cnt == N:
        col_info[j] = 1
    elif cnt == -N:
        col_info[j] = -1

if sum(col_info) == N:
    print(0)
    exit()
elif sum(col_info) == -N:
    print(-1)
    exit()

ans = 10**9
for i in range(N):
    ans_new = N - col_info.count(1)
    if col_info[i] == -1:
        ans_new += 1
    for j in range(N):
        if grid[i][j] == '.':
            ans_new += 1
    ans = min(ans, ans_new)

print(ans)

Submission status: Accepted

Solution code:
# - どの横一行を揃えるかで場合分け
#   - 上から i 行目を揃える場合、左から i 列目が # になっている行が必要
#     - もともとそのような行があるなら、i 行目を揃えるのに必要な操作回数は
#        N - (初期状態の i 行目の # の数)
#     - そのような行が無い場合、# のある適当な行を i 列目に置くことで作る
#       - 操作回数は N - (初期状態の i 行目の # の数) + 1
# - 横が一行以上揃ったら、縦を揃える
#   - 操作回数は N - (初期状態で揃ってる縦列の数)

N = int(input())
A = [input().replace("#", "1").replace(".", "0") for _ in range(N)]
A_T_bit = [int("".join(a), 2) for a in zip(*A)]

if A_T_bit.count(0) == N:
    print(-1)
    exit()
ans = float("inf")
for row, col in zip(A, A_T_bit):
    if col > 0:
        ans = min(ans, N - row.count("1"))
    else:
        ans = min(ans, N - row.count("1") + 1)
ans += N - A_T_bit.count((1<<N)-1)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [input() for _ in range(n)]
ans1 = float('inf')
for i in range(n):
    for j in range(n):
        if a[j][i] == '#':
            break
    else:
        continue
    break
else:
    print(-1)
    exit(0)
for i in range(n):
    cnt = 1
    for j in range(n):
        if a[j][i] == '#':
            cnt -= 1
            break
    for j in range(n):
        if a[i][j] == '.':
            cnt += 1
    ans1 = min(ans1, cnt)
ans2 = 0
for i in range(n):
    for j in range(n):
        if a[j][i] == '.':
            ans2 += 1
            break
if ans1 == float('inf'):
    print(-1)
else:
    print(ans1 + ans2)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N = int(input())
    a = np.array([[0 if c == "." else 1 for c in list(input().strip())] for i in range(N)])

    c = 0
    ok = [False] * N
    all_white = True
    for i in range(N):
        tmp = np.count_nonzero(a[:,i] == 0)
        if tmp > 0:
            c += 1
        if tmp != N:
            all_white = False
            ok[i] = True
    
    if all_white:
        print(-1)
        return
    
    ans = int(1e9)
    for i in range(N):
        if ok[i]:
            tmp = np.count_nonzero(a[i] == 0)
        else:
            tmp = np.count_nonzero(a[i] == 0) + 1
        ans = min(ans, tmp + c)
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
ii,jj=[0]*n,[0]*n
b=0
for i in range(n):
  s=input()
  for j in range(n):
    k=1if"#"==s[j] else 0
    ii[i]+=k
    jj[j]+=k
    b+=k
if b==0:print(-1);exit()
c=n-jj.count(n)
mi=10000
for i in range(n):
  x=n-ii[i]
  if jj[i]==0:x+=1
  mi=min(x,mi)
print(mi+c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

import numpy as np

buffer = sys.stdin.buffer
N = int(buffer.readline())
grid = np.frombuffer(buffer.read(),'S1').reshape(N,-1)[:,:N] == b'#'
if (~grid).all():
    print(-1)
    exit()

# 行ごとに、埋まった行を作る手数を計算する

cnt_row_op = np.sum(~grid,axis=1)
cnt_row_op += (~grid).all(axis=0)
answer = cnt_row_op.min() + np.sum((~grid).any(axis=0))
print(answer)