Maximum Laser Robots Placement

Robert is a famous engineer and has been tasked with a challenging problem. Given a map consisting of square blocks, where each block can be one of the three types:

• Wall: Blocks that lasers cannot pass through.
• Grass: Blocks that allow laser beams to pass.
• Empty: Blocks where a robot can be placed.

Each robot, when placed on an Empty block, continuously fires laser beams in the four cardinal directions (north, east, south, and west). However, the beams will travel through Grass cells but are halted by Walls. Two robots conflict if they are located along the same row or column without a Wall between them.

Your task is to compute the maximum number of robots that can be placed on the map without any two being in conflict.

Hint: This problem can be transformed into a bipartite matching problem. Divide the map into contiguous segments (separated by Walls) along rows and columns. Each empty cell belongs to one row segment and one column segment. Build a bipartite graph between these segments and find the maximum matching; this value is the maximum number of robots that can be placed.

All formulas should be represented in LaTeX format. For example, the bipartite matching relation can be expressed as \(\text{max robots} = \text{maximum matching}\).

inputFormat

The input begins with a line containing two integers \(R\) and \(C\) (the number of rows and columns respectively). Following this are \(R\) lines, each containing a string of length \(C\) that represents the map. The characters in the string are:

• 'W' for Wall
• 'G' for Grass
• 'E' for Empty

You can assume that \(1 \leq R, C \leq 100\).

outputFormat

Output a single integer representing the maximum number of robots that can be placed on the map without conflicts.

sample

3 3
EWE
EEE
EWE

3