在线网站seo优化,完成一个个人主页网站的制作,烟台做外贸网站建设,重庆市建设工程信息网证书查询审题#xff1a; 本题需要我们找出地毯的铺设方式并将铺设方式打印出来 要求#xff1a; 1.地毯不能互相覆盖 2.地毯不能铺设到障碍物#xff08;公主#xff09; 3.地毯必须铺满地#xff08;除了公主所在位置#xff09; 4.地毯坐标是拐角的坐标#xff08;行为x… 审题 本题需要我们找出地毯的铺设方式并将铺设方式打印出来 要求 1.地毯不能互相覆盖 2.地毯不能铺设到障碍物公主 3.地毯必须铺满地除了公主所在位置 4.地毯坐标是拐角的坐标行为x列为y 思路 方法一分治 我们不要一上来就直接分析最难的情况我们先分析k为1的情况 k为1也就是长度为2^1的情况此时矩阵为2*2 一共有四种情况我们只需要选择不包含障碍物的地毯即可 然后我们看看k为2的情况 此时我们其实可以将矩阵分为四部分每部分都是k为1的情况的矩阵对于包含公主的那一部分我们可以直接利用上情况1的方法对于其他三部分我们则可以铺设一块恰好包含这三部分的地毯从而让其他三部分都有障碍物进而可以完全利用k1的解决方法解决k2的问题 而我们的大问题可以分解为同样处理方法的小问题此时可以用递归算法 递归功能将对应矩阵的铺设方法打印出来 步骤 1.根据左上角坐标判断障碍物所在位置并铺设一块地毯覆盖其他三部分 2.利用递归函数解决如今四部分的地毯填补方案 3.当矩阵长度为1递归回溯 解题 #includeiostream
using namespace std;
int k,x,y;
void dfs(int x0, int y0, int len, int x, int y)
{if (len 1) return;len / 2;if (x x0 len y y0 len)//左上角情况{cout x0 len y0 len 1 endl;//地毯一dfs(x0, y0, len, x, y);dfs(x0, y0 len, len, x0 len - 1, y0 len);dfs(x0 len, y0, len, x0 len, y0 len - 1);dfs(x0 len, y0 len, len, x0 len, y0 len);}else if (x x0 len y y0 len)//右下角情况{cout x0 len-1 y0 len-1 4 endl;//地毯四dfs(x0, y0, len, x0 len - 1, y0 len - 1);dfs(x0, y0 len, len, x0 len - 1, y0 len);dfs(x0 len, y0, len, x0 len, y0 len - 1);dfs(x0 len, y0 len, len, x, y);}else if (x x0 len)//左下角情况{cout x0 len - 1 y0 len 3 endl;//地毯三dfs(x0, y0, len, x0 len - 1, y0 len - 1);dfs(x0, y0 len, len, x0 len - 1, y0 len);dfs(x0 len, y0, len, x, y);dfs(x0 len, y0 len, len, x0 len, y0 len);}else//右上角{cout x0 len y0 len -1 2 endl;//地毯三dfs(x0, y0, len, x0 len - 1, y0 len - 1);dfs(x0, y0 len, len, x, y);dfs(x0 len, y0, len, x0 len, y0 len - 1);dfs(x0 len, y0 len, len, x0 len, y0 len);}return;
}
int main()
{cin k x y;k (1 k);//变为2^kdfs(1, 1, k, x, y);//对指定矩阵填补地毯并输出填补数据return 0;
} P1228 地毯填补问题 - 洛谷
