Maximum Bishops Placement

Mr. Liu has been studying international chess using a software called jloi-08. In this software, besides playing a normal game with the computer and studying famous games or even beginner guides, there is a fun challenge: you are given a chessboard with some pieces already placed by the computer (these pieces might even attack each other, but you can ignore that). Your task is to place as many bishops as possible on empty cells such that:

• No two bishops (the ones you place) attack each other.
• No bishop you place attacks any of the pre-placed pieces.

Recall that in chess the bishop moves diagonally. Its attack range extends in the four diagonal directions until the first encountered piece blocks further movement. Formally, if a bishop is placed at cell \( (i,j) \), then in each of the four diagonal directions, it will attack the first piece encountered (if any). In our problem, if the first encountered piece in any diagonal from a bishop is either another bishop (placed by you) or a pre-placed piece, that bishop is considered to be attacking that piece, which is forbidden.

You are given an \( n \times m \) board. Each cell is either empty (represented by a .) or occupied by a pre-placed piece (represented by P). You may place a bishop on any empty cell provided that placing it does not make it attack any other piece (bishop or pre-placed) along any diagonal according to the chess rules. Note that the pre-placed pieces are fixed and also act as obstacles (blocking further view along that diagonal), but if a bishop sees a pre-placed piece as the first piece in any direction, that is not allowed.

Your task is to compute the maximum number of bishops that can be placed.

All formulas should be written in LaTeX format. For instance, the coordinate of a cell may be expressed as \( (i,j) \) and the bishop's move directions are given by \( (-1,-1) \), \( (-1,1) \), \( (1,-1) \), and \( (1,1) \).

inputFormat

The first line contains two integers \( n \) and \( m \) (the number of rows and columns of the board).

Then follow \( n \) lines, each containing a string of length \( m \). Each character is either . (indicating an empty cell) or P (indicating a pre-placed piece).

It is guaranteed that there will be at least 3 test cases, and the board sizes will be reasonably small so that a backtracking solution is feasible.

outputFormat

Output a single integer: the maximum number of bishops that can be placed on the board such that no two bishops attack each other and none of them attack any pre-placed piece.

sample

3 3
...
.P.
...

4