Non-attacking Knights

You are given an \(N \times M\) chessboard. Some of the cells on the board are forbidden for placing pieces. Your task is to place as many knights as possible on the board such that no two knights can attack each other. The knight moves in the standard chess manner (in an L-shape): specifically, from position \((i,j)\) it can move to any of the positions \((i \pm 2, j \pm 1)\) and \((i \pm 1, j \pm 2)\). Note that unlike some variants, there is no additional restriction (such as the 'horse leg' rule) in this problem.

Hint: The optimal configuration corresponds to the maximum independent set in a graph where vertices represent allowed cells and edges connect cells that are a knight's move apart. By partitioning the board into two colors (using \((i+j) \;\%\; 2\)), the problem can be transformed into a bipartite graph. Then by computing the maximum matching \(\mu\) using, for instance, the DFS method, the solution is given by:

[ \text{Answer} = \text{Total allowed cells} - \mu ]

inputFormat

The input consists of:

1. A line containing two integers \(N\) and \(M\) (\(1 \leq N, M \leq 50\)), representing the number of rows and columns of the chessboard.
2. Then \(N\) lines follow, each containing a string of length \(M\). Each character is either a dot . (denoting an allowed cell) or a hash # (denoting a forbidden cell).

outputFormat

Output a single integer representing the maximum number of knights that can be placed on the board without any two knights attacking each other.

sample

2 2
..
..

4