使用分治思想解决L型骨牌覆盖2x2棋盘问题

"笔记 2024年4月29日.pdf" 这篇笔记主要讨论了一个使用分治思想解决的2×2棋盘问题，其中涉及L型骨牌的覆盖和特殊方格的处理。问题的核心是找到一种方法，用L型骨牌完全覆盖一个包含特定数量特殊方格的2×2棋盘。 分治策略在此问题中的应用是通过将大问题分解为小问题来解决。首先，我们假设对于任意大小k的2×2棋盘问题，已经有了解决方案。然后逐步从小规模（例如k=1）的问题开始，逐步增加特殊方格的数量，寻找解决方案。 当k=1时，问题很简单，只有一个特殊方格。随着k增大到2，我们可以看到，除了原有的特殊方格外，还需要覆盖其他3个2×2的非特殊方格。通过放置L型骨牌，每个骨牌会新增3个特殊方格，从而将问题向原始状态靠拢。 递归过程中，我们需要理解k规模与k+1规模之间的联系。在无特殊方格的3个2×2子棋盘交界处放置一个L型骨牌，可以解决4个2×2的问题。递归边界是当k=0时，无需操作，因为棋盘已完全被一个L型骨牌覆盖。 为了实现这个算法，我们需要编写一个递归函数。函数输入包括棋盘的起始坐标、结束坐标以及当前的特殊方格数量。输出可以用一个二维数组来存储所需骨牌的位置。为了方便排序和输出，可以定义一个结构体来表示骨牌的拐点坐标，并使用标准库的sort函数对结构体数组进行排序。 结构体定义如下： 1. 定义一个名为`Point`的结构体，包含两个整型成员`xi`和`yi`，分别表示坐标。 2. 提供构造函数来初始化结构体实例。 3. 创建一个结构体数组，用于存储骨牌的拐点坐标。 递归函数的实现过程是： 1. 检查当前特殊方格的位置，根据情况放置L型骨牌。 2. 在递归过程中，将需要的骨牌坐标存储在输出的二维数组中。 3. 递归结束后，对二维数组进行排序，然后输出结果。 此外，笔记还提到了几种不同的数据结构，如基本数据类型数组、结构体数组和容器（如vector），它们都可以用来辅助实现算法，但具体选择哪种取决于实现的效率和便利性。 这个笔记探讨了如何使用分治策略解决一个涉及到L型骨牌覆盖2×2棋盘的问题，涵盖了递归函数设计、数据结构的选择以及问题的分解和边界条件的设定。