蓝桥杯省赛真题-剪邮票_蓝桥杯,如下图, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来,要求-CSDN博客

admin 1个月前 (04-07) 新闻中心 14 0

蓝桥杯省赛真题-剪邮票_蓝桥杯,如下图, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来,要求-CSDN博客

　　如【图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，则可以说明邮票没有连着

　　。看接下来的代码应该可以明白了！

　　到了这里，这个题目也讲解的差不多了。接下来同学可以看看完整了程序了哦^ - ^

相关推荐

网友评论

最新评论