分治法解决棋盘覆盖问题C++实现

"该资源提供了一个使用C++编程语言实现的棋盘覆盖问题的解决方案，采用了分治算法。代码在Visual Studio 2019环境下编写，目标是将一个N×N的棋盘用L形积木填充。算法通过不断将棋盘划分为四个等分，并在每个阶段根据特殊点位置放置积木，直至棋盘尺寸减小至2×2，此时直接填充。算法设计避免使用全局变量，而是通过参数传递当前状态。时间复杂度为O(n*n)，空间复杂度同样为O(n*n)。" 在这个问题中，主要的知识点包括： 1. **分治算法**：分治是一种解决复杂问题的策略，它将大问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题，然后递归地解决这些子问题，最后将子问题的解合并得到原问题的解。在这个棋盘覆盖问题中，算法不断将棋盘划分为4个等分，直到棋盘大小变为2×2。 2. **L形积木**：L形积木由三个相邻的正方形组成，可以覆盖棋盘上的三个格子。在划分过程中，算法会根据特殊点位置放置积木，确保每个棋盘单元被覆盖。 3. **递归**：在`trio`函数中，使用递归处理棋盘的划分和填充。当棋盘大小n=2时，调用`trio2`函数填充2×2的棋盘并结束递归。否则，根据特殊点位置放置积木，然后对四个子区域分别递归调用`trio`。 4. **参数传递**：为了避免使用全局变量，棋盘的状态（如当前位置、特殊点坐标、棋盘尺寸和已使用的符号数）作为参数传递。这增加了代码的清晰性和可维护性。 5. **时间复杂度和空间复杂度分析**：算法的时间复杂度为O(n*n)，表示处理棋盘的每个单元需要常数时间，总共需要遍历n*n个单元。空间复杂度同样为O(n*n)，因为需要存储棋盘的二维数组。 6. **C++编程基础**：代码使用了C++的基本语法，包括函数定义、指针、循环和条件语句。`char**board`表示二维字符数组，用于存储棋盘的状态，`'0'`代表未被覆盖，`cnt+'0'`则代表当前使用的积木符号。 7. **二维数组操作**：在`trio2`和`trio`函数中，通过对二维数组的遍历和赋值来填充棋盘，例如`board[x+i][y+j]`用于访问棋盘上的特定位置。 8. **逻辑判断**：代码中包含多个条件判断，以确定L形积木应如何放置，以及如何递归地处理子区域。例如，`if(by-ay>=n/2)`用来判断特殊点在棋盘的上半部分还是下半部分。 以上就是这个棋盘覆盖问题C++源码中涉及的主要知识点，它们涵盖了分治算法、递归、数据结构操作以及算法复杂度分析等多个编程和算法设计方面的概念。