Maximal Non-Attacking Knights Placement on a Chessboard

Given an \(n \times n\) chessboard where some cells are blocked by obstacles, determine the maximum number of knights (as in chess) that can be placed on the board so that no two knights can attack each other. A knight moves in an L-shaped pattern: \( (2,1), (2,-1), (-2,1), (-2,-1), (1,2), (1,-2), (-1,2), (-1,-2) \). Knights cannot be placed on cells with obstacles.

The problem can be approached by modeling the board as a bipartite graph where each free cell is assigned a color (based on \( (i+j) \% 2 \)). An edge is drawn between two cells if a knight placed on one cell can attack the other. By applying K\"onig's theorem, the maximum number of non-attacking knights is equal to the total number of free cells minus the size of the maximum matching in the bipartite graph.

inputFormat

The first line contains an integer \( n \) (\(1 \leq n \leq 100\)), the size of the chessboard.

The following \( n \) lines each contain a string of length \( n \) consisting only of the characters . and #, where . indicates a free cell and # indicates an obstacle.

outputFormat

Output a single integer representing the maximum number of knights that can be placed on the chessboard so that no two knights attack each other.

sample

1
.

1