def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx +=1 grid = [] for _ in range(N): grid.append(input[idx]) idx +=1 # Check for vertical possible (columns) vertical = [] for j in range(N): column = [grid[i][j] for i in range(N)] consecutive = 0 possible = False for c in column: if c == '.': consecutive +=1 if consecutive >= N-1: possible = True break else: consecutive = 0 if possible: vertical.append(j) v = len(vertical) # Check for horizontal possible (rows) horizontal = [] for i in range(N): row = grid[i] consecutive = 0 possible = False for c in row: if c == '.': consecutive +=1 if consecutive >= N-1: possible = True break else: consecutive = 0 if possible: horizontal.append(i) h = len(horizontal) # Build bipartite graph # Vertical on left (v nodes), horizontal on right (h nodes) # Create indices mapping vert_to_idx = {col: idx for idx, col in enumerate(vertical)} horz_to_idx = {row: idx for idx, row in enumerate(horizontal)} class BipartiteMatching: def __init__(self, n, m): self.n = n self.m = m self.graph = [[] for _ in range(n)] self.match_to = [-1] * m self.used = [False] * n def add_edge(self, u, v): self.graph[u].append(v) def dfs(self, v): self.used[v] = True for u in self.graph[v]: w = self.match_to[u] if w < 0 or (not self.used[w] and self.dfs(w)): self.match_to[u] = v return True return False def maximum_matching(self): res = 0 for v in range(self.n): if self.used[v]: continue self.used = [False] * self.n if self.dfs(v): res += 1 return res bm = BipartiteMatching(v, h) for vert_col in vertical: vidx = vert_to_idx[vert_col] for horz_row in horizontal: hidx = horz_to_idx[horz_row] if grid[horz_row][vert_col] == '.': bm.add_edge(vidx, hidx) max_matching = bm.maximum_matching() result = v + h - max_matching print(result) if __name__ == '__main__': main()