[二分图]JZOJ 4612 游戏

Description

 

Input

Output

 

Sample Input

4 4
#***
*#**
**#*
xxx#

Sample Output

5

 

Data Constraint

分析

非常眼熟，行列唯一匹配，可以想到二分图

只是多了大石头的干扰，那么我们把所有的行联通和列联通求出连边即可

注意软石头不能连接它所在的行列，但是可以让行联通或列联通