在这个问题中,涉及到对大小为NxN的棋盘进行填充,使用的方法是L形积木结构,而解决方案则采用C++中的分治法。通过在vs2019环境下进行实验,题目为棋盘覆盖。问题的核心在于对棋盘的不断划分,每次划分前根据特殊块的位置放置一个积木,直到棋盘的长度足够小(n=2)时,停止划分并开始填充。为了实现这一过程,不使用全局变量,而是通过参数传递的方式传递必要的信息,如当前棋盘起点坐标(ax,ay)、特殊点坐标(bx,by)、棋盘长度n、二维棋盘board以及当前使用的符号数cnt。设计了函数trio,其中将n=2作为递归出口,若n不等于2,则根据特殊点位置放置一个积木,然后将棋盘四等分,继续递归。对算法进行复杂度分析,得出时间复杂度为O(nn),空间复杂度为O(nn)。
用户评论
推荐下载
-
矩阵乘法分治法
利用分治法求解矩阵乘法,可以使复杂度降低
17 2019-07-09 -
矩阵相乘分治法
实验目的:掌握分冶策略的基本思想以及用分冶法解决问题的一般技巧.运用编程工具,并运用分冶法来解决矩阵乘法问题;2.实验内容:设A和B是两个n*n阶矩阵,求它们的乘积矩阵C。这里,假设n是2的幂次方;
29 2019-07-09 -
分治法求众数
分治法求众数
38 2019-07-10 -
凸包分治法
分治法求解凸包问题一个简单的程序实验报告可以用
14 2019-07-11 -
分治法实现排序
利用分治法进行对2的次方个数排序,次方数由用户输入,其中包括源码,运行程序与截图,读者可以进行自行修改进行其他数字的排序
40 2019-01-02 -
分治法_中位数
分治法-中位数 第一行: n,为x和y数组的元素个数 第二行: x数组的n个数,用空格分隔 第三行: y数组的n个数,用空格分隔
52 2019-01-01 -
优化方法单纯形法C++程序
优化方法单纯形法 C++程序 水平有限,仅供参考
18 2020-09-27 -
C++实现的直线填充算法
用Visual C++的实现的填充算法,有源代码
8 2020-09-17 -
棋盘覆盖问题的C++源程序
盘覆盖问题:在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊
28 2019-01-04 -
多边形填充
多边形填充 计算机图形学 c++ 代码加文档
26 2019-01-12
暂无评论