题目描述
图一
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路：直接搜索感觉很难实现,我们可以转换成全排列的方式.一共12张,我们需要五张,我们可以创建一个数组,存放5个0,7个1,然后我们对其进行全排列(使用C++STL中的next_permutation()),然后转变成二维数组(并不是真的搞一个二维数组,直接用一维数组和二维数组坐标之间的关系来进行模拟就可)进行DFS,最后统计其数值为0的连通块的个数,如果为个数1说明该排列符合.
在比赛时,如果不放心可以遍历数组进行测试一把.代码中这部分进行了注释.
还有根据经验一旦用到了DFS,或者递归,其中的变量一定要定义成局部变量,定义成全局很可能会出现很奇怪的结果.
参考代码
#include<bits/stdc++.h> using namespace std; int arr[12] = {0,0,0,0,0,1,1,1,1,1,1,1},book[12],total,cnt; int NEXT[4][2] = {//方向数组 -1,0, 0,1, 1,0, 0,-1 }; void print()//用于验证 { cout<<"-------------------"<<endl; for(int i = 0; i < 12; i++){ if(i % 4 == 0){ cout<<endl; } cout<<arr[i]<<"\t"; } cout<<endl; cout<<"-------------------"<<endl; } void dfs(int m) { if(arr[m]==1){//结束条件 return; } int x = m / 4;//转换成二维数组中的坐标 int y = m % 4; for(int i = 0; i <4; i++) { int tx = x + NEXT[i][0]; int ty = y + NEXT[i][1]; if(tx < 0 || tx > 2 || ty < 0 || ty > 3)//判断是否越界 { continue; } int k = 4 * tx + ty;//转成一位数组坐标进行下一步DFS. if(book[k]==0){ book[k] = 1;//做标记 这个操作放在这里或者放到DFS的最开始都行. dfs(k); } } return; } int main() { do{ cnt = 0; memset(book,0,sizeof(book));//记得memset对于int数组只能初始化成0或者-1,不要作作.乱初始化 for(int i = 0; i < 12; i++) { if(!arr[i]&&!book[i]){ book[i] = 1; dfs(i);//把坐标传进去 cnt++; } } if(cnt==1){ // if(total<=20){//用于验证数据 // print(); // } total++; } }while(next_permutation(arr,arr+12)); cout<<total<<endl; return 0; }
答案:116
