本文共 711 字，大约阅读时间需要 2 分钟。
城市规划问题要求在n x n地图中放置最大数量的堡垒，且任何两个堡垒不能在同一行或同一列，除非它们能被墙阻挡。这个问题可以通过建立二分图并求最大匹配来解决。
一、问题理解
地图分析：每个格子要么是可用的地带（.），要么是墙（X）。 限制条件：同一行或列的两个堡垒必须满足：要么之间有墙阻挡，要么它们不在同一行或列。 二、建模思路
分割为行和列：将行和列的可行位置分别作为二分图的两个部分，节点表示可行的位置。 建立边：在行列节点之间创建边，当且仅当一行位置可以与一列位置互不干扰（即它们之间没有互相攻击的可能）。 求最大匹配：找到二分图中的最大匹配，这个数对应最多的堡垒位置。 三、建图过程
初始化：根据地图构建行和列的可行列表，记录每个位置前一个非墙的位置，确定可行区间。 松弛匹配：使用深度优先搜索遍历行和列的可行位置，找到对应的匹配。判断两个位置是否符合互不攻击的条件，创建边。 计算匹配数：逐个检查每个行位置的可用列位置，找到最大的匹配数目。 四、优化思路
剪枝机制：在遍历时，避免重复检查已访问过的节点，提高效率。 回溯法：使用深度优先搜索，确保在找到所有可能的匹配时，能正确回溯并更新最大值。 五、测试与验证
样例验证：将输入数据代入代码，验证样例输出是否正确。例如，4x4地图输出应为5。 极端情况分析：测试全墙地图、全开地图等特殊情况下堡垒的数量是否正确。 调试与技巧：遇到错误时，逐步剪枝，检查条件逻辑，确保边的建立正确无误。 六、结论
通过构建二分图并求最大匹配，可以有效解决这个城市规划问题。代码的逻辑清晰，使用深度优先搜索有助于高效地找到最优解。通过严格的测试和验证，最终可获得正确的最多堡垒数目。
转载地址：http://kwkoz.baihongyu.com/