import sys from collections import deque, defaultdict def main(): sys.setrecursionlimit(1 << 25) N = int(sys.stdin.readline()) grid = [] for _ in range(N): line = sys.stdin.readline().strip() grid.append(list(line)) # Generate H trombones h = [] for i in range(N): max_j = N - (N-1) for j in range(max_j): valid = True for k in range(N-1): if j + k >= N: valid = False break if grid[i][j + k] != '.': valid = False break if valid: h.append((i, j)) # Generate V trombones v = [] for j in range(N): max_i = N - (N-1) for i in range(max_i): valid = True for k in range(N-1): if i + k >= N: valid = False break if grid[i + k][j] != '.': valid = False break if valid: v.append((j, i)) # Preprocess V into columns v_list = [] for (j, i) in v: i_end = i + (N-2) v_list.append((j, i, i_end)) v_col = defaultdict(list) for idx, (j, i, i_end) in enumerate(v_list): v_col[j].append((i, i_end, idx)) # Build adjacency list H = len(h) V = len(v) adj = [[] for _ in range(H)] for H_idx, (i_h, j_h) in enumerate(h): h_len = N-1 for k in range(j_h, j_h + h_len): if k >= N: continue if k not in v_col: continue vs = v_col[k] for (i_v, i_v_end, v_idx) in vs: if i_v <= i_h <= i_v_end: adj[H_idx].append(v_idx) # Hopcroft-Karp algorithm pair_U = [-1] * H pair_V = [-1] * V dist = [0] * H def bfs(): queue = deque() for u in range(H): if pair_U[u] == -1: dist[u] = 0 queue.append(u) else: dist[u] = float('inf') dist_found = float('inf') while queue: u = queue.popleft() if dist[u] < dist_found: for v in adj[u]: if pair_V[v] == -1: dist_found = dist[u] + 1 elif dist[pair_V[v]] == float('inf'): dist[pair_V[v]] = dist[u] + 1 queue.append(pair_V[v]) return dist_found != float('inf') def dfs(u): for v in adj[u]: if pair_V[v] == -1 or (dist[pair_V[v]] == dist[u] + 1 and dfs(pair_V[v])): pair_U[u] = v pair_V[v] = u return True dist[u] = float('inf') return False result = 0 while bfs(): for u in range(H): if pair_U[u] == -1: if dfs(u): result += 1 X = (H + V) - result print(X) if __name__ == '__main__': main()