如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。
请你计算,一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。 1.1排列
看到这个题目,便很容易想到全排列,因为要剪5张连在一起的邮票,则可以用一个数组a[12]来标记,其中5个数为1,其余全为0。
这里全排列推荐使用,可以去除重复的排列方式,而用递归回溯的方法还要考虑去重。
要注意的是:
1.2转换成二维数组
上面给邮票进行了全排列,下面则要将次数列转换为二维数组进行连通的检测,当然也可将
第一张邮票进行标记,为接下来寻找其他邮票做好准备。
1.3核心DFS
到了这里,已经到了本题最关键的位置,下面举个荔枝,加深对这个的理解
例如:
通过cc(1,1)函数传来,然后将这点标记,
然后进入的dfs(2,1)函数,如果 ss[2][1]==0 ,也就是没有标记点
则返回dfs()函数,也就是dfs(1,1),继续执行未完成的语句,也就是dfs(1,2),
如果也没有找到标记点,就又返回dfs(1,1),继续执行(dfs0,1),
如果没有还没有标记点,则返回dfs(1,1),继续执行dfs(1,0)
如果还是没有标记点,则dfs(1,1)已经执行完成了.
那么接下来dfs(1,1)要返回了,便回到cc()函数,继续执行未完成的语句,
也就是 int flag=0的位置,直到cc()函数结束
1.4判断是否连接
接着上面的思路,我们不难发现,如果有1个数没有标记成0,则可以说明邮票没有连着
。看接下来的代码应该可以明白了!
到了这里,这个题目也讲解的差不多了。接下来同学可以看看完整了程序了哦^ - ^
网友评论
最新评论