P2825 [HEOI2016/TJOI2016] Game

In 2016, Sister Jiayuan fell in love with a game called BnB. Simply put, in this game you place several bombs on a map to see whether you can hit the opponent or avoid the opponent’s bombs. While playing, Little H thought of this question: given a map, what is the maximum number of bombs you can place so that no two bombs can hit each other? A bomb’s explosion reaches the entire row and column where it is placed. The explosion can pass through soft stones, but cannot pass through hard stones. You are given an $ n \times m $ grid map: the symbol ``*`` denotes an empty cell; the explosion can pass through it, and you can place a bomb on it. The symbol ``x`` denotes a soft stone; the explosion can pass through it, but you cannot place a bomb on it. The symbol ``#`` denotes a hard stone; the explosion cannot pass through it, and you cannot place a bomb on it. For example, given a $ 1 \times 4 $ grid map ``*xx*``, you can place at most one bomb on this map. Given another $ 1 \times 4 $ grid map ``*x#*``, you can place at most two bombs on this map. Now, given any $ n \times m $ grid map from Little H, determine the maximum number of bombs that can be placed.

The first line contains two positive integers $ n, m $, where $ n $ is the number of rows and $ m $ is the number of columns. Then $ n $ lines follow, each containing $ m $ characters representing the grid map. The number of ``*`` does not exceed $ n \times m $.

Output a single integer $ a $, the maximum number of bombs that can be placed.

$1 \leq n, m \leq 50$. Translated by ChatGPT 5