棋盘问题-寻找伪码算法（分而治之）

Question

我应该使用分而治之的范式设计递归算法“ CBCover”，该算法确定运行时O（n ^ 2）（n = 2 ^ k）的覆盖范围（如下图所示）。 >

CBCover的输入/输入应为（k，a，b），其中k定义棋盘的大小，（a，b）是缺失字段的坐标。

可能的覆盖范围：

缺少4x4棋盘（4，1）：

<<

有人知道

伪代码

的样子吗？我应该使用分而治之范式设计递归算法“ CBCover”，该算法确定运行时O（n ^ 2）（n = 2 ^ k）的覆盖范围（如下图所示）。 ...

Answer 1

算法可以如下：

确定四个象限中的哪个象限缺少字段。将L形片放置在网格的中心，使其在其他三个象限的每个象限中占据一个场。现在，您有四个象限，每个象限都不能再使用了。应用相同的策略递归求解每个象限。当前网格没有可用字段时，递归将停止，即，它是一个1x1网格，其中包含一个不可用的字段。