Minimum Cameras Needed

You are given a grid of size \(n \times m\) consisting of characters '.' (empty space) and '#' (pillar). A camera can be placed on an empty cell ('.'). When a camera is placed at position \( (i,j) \), it covers its entire row and column until its vision is blocked by a pillar. However, for the purpose of this problem, you only need to ensure that every row and every column which is not completely filled with pillars has at least one camera.

More formally, you must place cameras such that for every row \(i\) that is not exclusively composed of '#' characters, there is at least one camera in that row, and similarly for every column \(j\) that is not completely filled with '#' characters. Note that if an entire row or column consists only of pillars (i.e. all '#' characters), then it is considered already covered.

Your goal is to determine the minimum number of cameras required to achieve this.

Note: A camera placed at position \( (i,j) \) covers row \(i\) and column \(j\). The camera cannot be placed on a pillar.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m
row1
row2
...
rown

Here, \(n\) and \(m\) are integers representing the number of rows and columns respectively. Each of the next \(n\) lines contains a string of length \(m\) representing a row of the grid.

outputFormat

Output to standard output (stdout) a single integer which is the minimum number of cameras needed to ensure each applicable row and column is covered.

4 4
.#..
...#
.#..
....

4