题目理解

我们有一个 $n \times m$ 的网格地图，包含三种格子：

• *：空地，可以放炸弹，炸弹威力可以穿透
• x：软石头，不能放炸弹，但炸弹威力可以穿透
• #：硬石头，不能放炸弹，且炸弹威力不能穿透

炸弹的爆炸范围是整行和整列，但遇到硬石头会阻断。

我们需要找到最多能放置的炸弹数量，使得任意两个炸弹不会互相炸到（即不在同一行/列，除非被硬石头隔开）。

问题分析

关键观察

这个问题类似于二分图最大匹配问题，但需要处理硬石头的阻断效果。

重要性质：

• 硬石头 # 会将一行或一列分割成多个独立的"区域"
• 每个可以放置炸弹的空地 * 属于某个行区域和某个列区域
• 两个炸弹不会互相炸到，当且仅当它们不在同一个行区域且不在同一个列区域

问题转化

我们可以将问题转化为：

1. 将每行根据硬石头分割成多个行区域
2. 将每列根据硬石头分割成多个列区域
3. 每个空地 * 连接它所在的行区域和列区域
4. 求这个二分图的最大匹配

解法思路

二分图建模

建图过程：

1. 行区域编号：遍历每一行，遇到硬石头就开启新的区域编号
2. 列区域编号：遍历每一列，遇到硬石头就开启新的区域编号
3. 连边：对于每个空地 *，在它所在的行区域和列区域之间连边

最大匹配：

• 行区域作为左部点
• 列区域作为右部点
• 空地作为边
• 求二分图最大匹配即为最多能放置的炸弹数

算法选择

使用匈牙利算法求二分图最大匹配：

• 时间复杂度：$O(n \cdot m \cdot (n+m))$，对于 $n, m \leq 50$ 是可接受的

算法复杂度分析

• 区域编号：$O(n \cdot m)$
• 建图：$O(n \cdot m)$
• 匈牙利算法：$O(E \cdot V) = O(n \cdot m \cdot (n+m))$
• 总复杂度：对于 $n, m \leq 50$ 是可接受的

关键技巧总结

1. 区域分割：利用硬石头将行列分割成独立区域
2. 二分图建模：将问题转化为经典的最大匹配问题
3. 匈牙利算法：求解二分图最大匹配的标准算法

正确性证明

为什么这样建模是正确的？

1. 安全性：如果两个炸弹在同一个行区域，它们会互相炸到（除非被硬石头隔开，但同一区域内的炸弹不会被硬石头隔开）
2. 完备性：任何不互相炸到的炸弹放置方案都对应一个匹配
3. 最优性：最大匹配对应最优的炸弹放置方案

形式化证明：

• 每个炸弹占据一个行区域和一个列区域
• 两个炸弹冲突当且仅当它们共享行区域或列区域
• 这正好对应二分图中两条边共享端点
• 因此最大匹配就是最大独立集

样例验证

对于样例：

#***
*#**
**#*
xxx#

行区域划分：

行1: [#] [***]        → 2个区域
行2: [*] [#] [**]     → 3个区域  
行3: [**] [#] [*]     → 3个区域
行4: [xxx#]           → 1个区域
共9个行区域

列区域划分：
列1: [#***]           → 1个区域
列2: [*#*x]           → 1个区域
列3: [**#x]           → 1个区域
列4: [***#]           → 1个区域
共4个列区域

建图后求最大匹配为5，与样例输出一致。

这种方法通过巧妙的区域划分和二分图建模，将复杂的放置问题转化为经典的最大匹配问题，实现了高效的求解。