Mujin Programming Challenge 2017 - Row to Column

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 `#`.

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.

Examples

Input

2
#.
.#


Output

3


Input

2
.
.#


Output

3


Input

2
..
..


Output

-1


Input

2


Output

0


Input

3
.#.

.#.


Output

2


Input

3
...
.#.
...


Output

5

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
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
	black_cnt = [0] * n
	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()


n = int(input())
a = eval('list(input()),' * n)
f = sum((n == t.count('#') for t in zip(*a)))
print(-all((t.count('#') < 1 for 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))))


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


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)


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


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)


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)


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)


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)


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


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)


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)


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)


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)


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)


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


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
	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)
solve()


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


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)


(n, *a) = open(0).readlines()
n = int(n)
(*b,) = zip(*a)
(f, e) = [sum(((c in t) ^ 1 for 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))))


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)


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)


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)


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)


n = int(input())
a = eval('list(input()),' * n)
if all((t.count('#') < 1 for 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)


n = int(input())
(ii, jj) = ([0] * n, [0] * n)
b = 0
for i in range(n):
	s = input()
	for j in range(n):
		k = 1 if '#' == 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)


N = int(input())
a = [[str == '#' for str in input()] for _ 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)


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)


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


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)


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)


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)