from collections import deque def main(): N = int(input()) grid = [input().strip() for _ in range(N)] # For each column, find all possible vertical trombone ranges (1-based) vert_available = [] # vert_available[c] is list of (start, end) for column c (0-based) for c in range(N): ranges = [] max_i = N - (N - 1) for i in range(max_i): start_row = i + 1 # 1-based end_row = start_row + (N - 1) - 1 valid = True for row in range(start_row - 1, end_row): # convert to 0-based if row >= N or grid[row][c] == '#': valid = False break if valid: ranges.append((start_row, end_row)) vert_available.append(ranges) C = [c for c in range(N) if vert_available[c]] # For each row, find all possible horizontal trombone ranges (1-based) horiz_available = [] # horiz_available[r] is list of (start, end) for row r (0-based) for r in range(N): ranges = [] max_j = N - (N - 1) for j in range(max_j): start_col = j + 1 # 1-based end_col = start_col + (N - 1) - 1 valid = True for col in range(start_col - 1, end_col): # convert to 0-based if col >= N or grid[r][col] == '#': valid = False break if valid: ranges.append((start_col, end_col)) horiz_available.append(ranges) R = [r for r in range(N) if horiz_available[r]] # Build edges between columns in C and rows in R if they intersect edges = [] for c in C: for r in R: # Check if row r+1 (1-based) is in any vertical range of column c current_r_1based = r + 1 in_vert = False for (start, end) in vert_available[c]: if start <= current_r_1based <= end: in_vert = True break if not in_vert: continue # Check if column c+1 (1-based) is in any horizontal range of row r current_c_1based = c + 1 in_horiz = False for (start, end) in horiz_available[r]: if start <= current_c_1based <= end: in_horiz = True break if in_horiz: edges.append((c, r)) # Build adjacency list for bipartite graph graph = {c: [] for c in C} for c, r in edges: graph[c].append(r) # Hopcroft-Karp algorithm implementation def hopcroft_karp(): pair_U = {u: None for u in C} pair_V = {v: None for v in R} dist = {} def bfs(): queue = deque() for u in C: if pair_U[u] is None: dist[u] = 0 queue.append(u) else: dist[u] = float('inf') dist[None] = float('inf') while queue: u = queue.popleft() if u is not None: for v in graph[u]: if dist.get(pair_V.get(v, None), float('inf')) == float('inf'): dist[pair_V.get(v, None)] = dist[u] + 1 queue.append(pair_V.get(v, None)) return dist.get(None, float('inf')) != float('inf') def dfs(u): if u is not None: for v in graph[u]: if dist.get(pair_V.get(v, None), float('inf')) == dist[u] + 1: if dfs(pair_V.get(v, None)): pair_U[u] = v pair_V[v] = u return True dist[u] = float('inf') return False return True result = 0 while bfs(): for u in C: if pair_U[u] is None: if dfs(u): result += 1 return result max_matching = hopcroft_karp() X = len(C) + len(R) - max_matching print(X) if __name__ == "__main__": main()