博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
分治法之棋盘覆盖问题
阅读量:5172 次
发布时间:2019-06-13

本文共 2392 字,大约阅读时间需要 7 分钟。

写此博文目的:

1.刚学了棋盘覆盖问题,自己实现它,加深自己的理解很感悟

2.给为棋盘问题困惑的朋友带来一点思路

 

开始分析!

 

什么叫做分治法呢?

:简单来说就是分而治之,先把问题分解成很多个小问题,然后再处理它

棋盘覆盖问题就是一个很经典的分治问题

首先我们先来看一下棋盘覆盖问题到底是个什么问题?

题目引用自:

思路分析:

将一个大的棋盘划分为相同大小的四块,在这四块相同大小的子棋盘中,现在只有一个子棋盘有一个格子是不可覆盖的,还有三个子棋盘是所有的格子都是可以覆盖的,所以我们需要为这3个不存在不可覆盖格子的子棋盘构造3个不可覆盖的格子,那么我们应该如何构造呢?

下面我们看一张图:

假如现在第一个不可覆盖的格子在左上角,那么我们需要构造的3个不可覆盖的格子就跟上面的图一样,构造的这3个不可覆盖的格子的连接成的形状肯定是个L型,只是会随着棋盘中不可覆盖的格子的位置的不同而L型的开口方向会有所变化

总结一下:

2k2k2k∗2k的棋盘划分为2k12k12k−1∗2k−1这样的子棋盘4块。递归填充各个格子,填充分为四个情况,归出口为s=0,s=0也就是子棋盘方格数为1。

递归的四种情况:

如果黑方块在左上子棋盘,则递归填充左上子棋盘;否则填充左上子棋盘的右下角,将右下角看做黑色方块,然后递归填充左上子棋盘。

如果黑方块在右上子棋盘,则递归填充右上子棋盘;否则填充右上子棋盘的左下角,将左下角看做黑色方块,然后递归填充右上子棋盘。

如果黑方块在左下子棋盘,则递归填充左下子棋盘;否则填充左下子棋盘的右上角,将右上角看做黑色方块,然后递归填充左下子棋盘。

如果黑方块在右下子棋盘,则递归填充右下子棋盘;否则填充右下子棋盘的右下角,将左上角看做黑色方块,然后递归填充右下子棋盘。

好啦,话不多说,我们直接撸代码吧!!!

1 #include
2 #define max 1024 3 int cb[max][max];//最大棋盘 4 int id=0;//覆盖标志位 5 int chessboard(int tr,int tc,int dr,int dc,int size)//tr,tc代表棋盘左上角的位置,dr ,dc代表棋盘不可覆盖点的位置,size是棋盘大小 6 { 7 if(size==1)//如果递归到某个时候,棋盘大小为1,则结束递归 8 { 9 return 0;10 }11 int s=size/2;//使得新得到的棋盘为原来棋盘大小的四分之一12 int t=id++;13 if(dr
=tc+s)//如果不可覆盖点在右上角,就对这个棋盘右上角的四分之一重新进行棋盘覆盖23 {24 chessboard(tr,tc+s,dr,dc,s);25 }else//因为不可覆盖点不在右上角,所以我们要在右上角构造一个不可覆盖点26 {27 cb[tr+s-1][tc+s]=t;28 chessboard(tr,tc+s,tr+s-1,tc+s,s);//在我们构造完不可覆盖点之后,棋盘的右上角的四分之一又有了不可覆盖点,所以就对右上角棋盘的四分之一进行棋盘覆盖29 }30 31 32 if(dr>=tr+s&&dc
=tr+s&&dc>=tc+s)//如果不可覆盖点在右下角,就对这个棋盘右下角的四分之一重新进行棋盘覆盖42 {43 chessboard(tr+s,tc+s,dr,dc,s);44 }else//因为不可覆盖点不在右下角,所以我们要在右下角构造一个不可覆盖点45 {46 cb[tr+s][tc+s]=t;47 chessboard(tr+s,tc+s,tr+s,tc+s,s);//在我们构造完不可覆盖点之后,棋盘的右下角的四分之一又有了不可覆盖点,所以就对右下角棋盘的四分之一进行棋盘覆盖48 }49 50 //后面的四个步骤都跟第一个类似51 }52 int main()53 {54 printf("请输入正方形棋盘的大小(行数):\n");55 int n;56 scanf("%d",&n);57 printf("请输入在%d*%d棋盘上不可覆盖点的位置:\n",n,n);58 int i,j,k,l;59 scanf("%d %d",&i,&j);60 printf("不可覆盖点位置输入完毕,不可覆盖点的值为-1\n");61 cb[i][j]=-1;62 chessboard(0,0,i,j,n);63 for(k=0;k

代码分析:

我们先看chessboard函数

函数的主干是四个if else循环,也就是说只会执行一个if中的语句,但是会执行3个else中的语句,这3个else中的语句就是构造不可覆盖格子,然后对含有新构造的不可覆盖点的子棋盘来重写进行棋盘覆盖,也就是递归调用棋盘覆盖函数,递归的结束条件就是子棋盘只有一个格子,也就是s=1,每次调用棋盘覆盖函数,都要进行s=size/2,目的就是把一个大棋盘划分为四个相同大小的子棋盘。

运行结果:

 

不足错误的地方,欢迎各位拍砖指正哦!!!!!

技术在于分享

转载于:https://www.cnblogs.com/yinbiao/p/8666209.html

你可能感兴趣的文章
qcow2、raw、vmdk等镜像格式
查看>>
Jzoj5455【NOIP2017提高A组冲刺11.6】拆网线
查看>>
特定字符序列的判断(1028)
查看>>
华为面试
查看>>
平衡二叉树(AVL Tree)
查看>>
【BZOJ3295】[Cqoi2011]动态逆序对 cdq分治
查看>>
【CF799E】Aquarium decoration 线段树
查看>>
大运飞天 鲲鹏展翅
查看>>
从ECMA到W3C
查看>>
软件工程--第十六周学习进度
查看>>
yii2 ActiveRecord多表关联以及多表关联搜索的实现
查看>>
搜狗输入法安装--ubuntu
查看>>
ps/2接口键盘的输入及显示
查看>>
Swift———a Glance(极客学院)笔记
查看>>
【poj3294-不小于k个字符串中最长公共子串】后缀数组
查看>>
java如何获取其它用户登录的真是IP地址
查看>>
Jquery通过指定层次关系获取元素
查看>>
c# for 和 foreach 的区别
查看>>
docfx (一)
查看>>
HashMap底层实现原理/HashMap与HashTable区别/HashMap与HashSet区别
查看>>