当前位置 博文首页 > 爱新觉罗?炒饭的博客:2016年第七届蓝桥杯省赛C /C++ A组 剪邮票
剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。
请你计算,一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
解法1:
#include<iostream>
#include<cstring>//memset函数的头文件
#include<algorithm>//next_permutation函数的头文件
using namespace std;
int a[12]={1,1,0,1,1,0,0,1,0,0,0};
int map[3][4];//map数组用坐标表示数字
int ans=0;//记录个数
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//四个方向分别是左,右,上,下
void dfs(int x,int y)
{
if(x<0||x>2||y<0||y>3) return;
if(map[x][y]==0) return;
map[x][y]=0;//当该数字记录为1时,表示剪当前数字,并将该数字记录为0
for(int i=0;i<4;i++)
dfs(x+dir[i][0],y+dir[i][1]);
}
bool judge()
{
int k=0;
int x,y;
for(int i=0;i<3;i++)
{
for(int j=0;j<4;j++)
{
if(a[k])//五个数字中任何一个都可以当起点
{
x=i;
y=j;
}
map[i][j]=a[k++];//将a数组里的数字转换到map数组里
}
}
dfs(x,y);
int flag=0;
for(int i=0;i<3;i++)
{
for(int j=0;j<4;j++)
{
if(map[i][j])
flag=1;
}
}
if(flag==1)
return false;
return true;
}
int main()
{
sort(a,a+12);
memset(map,0,sizeof(map));//初始化为0
do
{
if(judge())
{
ans++;
}
}while(next_permutation(a,a+12)) ;
cout<<ans<<endl;
return 0;
}
该解法我觉得是比较方便的,采用的是全排列的方法,a[12]数组中的5个1表示裁剪的数,将该数组利用next_permutation()函数全排列出来,然后将5个被裁的数字在map中用坐标表示,并且置为1,然后随便用一个被剪的数当起点,一次遍历到该数在map数组中的位置的左右上下四个方向,将能连接的数字全部遍历到,并将遍历到的数字全部置为0;然后再检查map数组中是否还有不为0的数(即为1),若有则这种排列不成功,说明有数字遍历不到,裁剪不成功,然后继续下一种排列即可。
cs