题目
剪邮票【2016 第七题】
.题目描述 如【图 1.jpg】, 有 12 张连在一起的 12 生肖的邮票。 现在你要从中剪下 5 张来，要求必须 是连着的。 （仅仅连接一个角不算相连） 比如，【图 2.jpg】，【图 3.jpg】中，粉红色所 示部分就是合格的剪取。 请你计算，一共有多少种不同的剪取方法。 请填写表示方案数目的整数。 注意：你提交的应该是一个整数，不要填写任何多余的内容 或说明性文字。
答案：116
思路：写得很暴力，代码多一点，但非常好懂
1从1~12中选5个数
2把这5个数转成坐标
3判断连通性
选出5个组合数——排列组合
用dfs实现，从1~12中选出5个数，要注意不要出现重复的组合，
void dfs(int num)//选5个数
{
if(num==6)
{
if(Check()) ans++;//选了5个数，并且判断连通
return ;
}
for(int i=1;i<=12;i++)
{
if(!vis[i])
{
if(i>tmp[num-1]) //这里很关键，防止出现重复的组合数
{
vis[i] = 1;//数字i选过了
tmp[num] = i;// 把数字i存入 ，tmp数组中的第num-1个数
dfs(num+1);
vis[i] = 0;//回溯
}
}
}
}
数字转坐标
坐标转换思路非常简单，就是按照邮票上的数字的位置转换
mp[i][j]数组代表邮票
因为有3行，所以 这里分3种情况
1数字number: 1~4，mp[1][number] = 1
2数字number:5~8, mp[2][number-4] = 1
3数字number:9~12,mp[3][number-8] = 1
必须提取到起始点，即选中的5个数中的任意一个数的坐标，我这里记录的第一个
int Check()//先进行坐标转换 ，
//这里非常简单，就是1234在第1行 ，5678第二行，9 10 11 12第3行
{
memset(mp,0,sizeof(mp));
int flag = 1;
int sx,sy;//记录起始点，必须从从这里出发，找到连通的5个数即可
for(int i=1;i<=5;i++)
{
if(tmp[i]>=1&&tmp[i]<=4) //如果1<=tmp[i]<=4 .那么肯定在第一行
{
mp[1][tmp[i]] = 1;
if(flag)
{
sx=1,sy=tmp[i],flag=0;
}
}
else if(tmp[i]>=5&&tmp[i]<=8)//如果5<=tmp[i]<=8 .那么肯定在第二行
{
mp[2][tmp[i]-4] = 4;
if(flag)
{
sx=2,sy=tmp[i]-4,flag=0;
}
}
else //如果9<=tmp[i]<=12 .那么肯定在第三行
{
mp[3][tmp[i]-8] = 1;
if(flag)
{
sx=3,sy=tmp[i]-8,flag=0;
}
}
}
g = 1;//从起始点出发，自然加个1
memset(vis2,0,sizeof(vis2));
vis2[sx][sy] = 1;
if(Check_dfs(sx,sy)==5) return 1;//如果是5个连通的数，则返回1
else return 0;
}
判断是否连通
用dfs实现，你从选中的5个数中的任意一个出发，
因为已经把选中的5个数对应的坐标在mp数组里标记为1，
1代表可以走，0代表不能。
从sx,sy出发，走一个点则，g++,如果g==5,那么则代表这5个数连通
否则g不可能为5
比如，选中1 6 7 10 11
你从数字1的位置（1，1）出发，上下左右都不能走，dfs直接结束了g=1。
从数字6出发，g=4,!=5,也不满足
int Check_dfs(int x,int y)//判断连通
{
for(int i=0;i<4;i++)
{
int x2 = x + dx[i];
int y2 = y + dy[i];
//mp数组里为1，代表选出的5个数，即可走的数，看这5个数是否连通
if(mp[x2][y2]&&x2>=1&&x2<=3&&y2>=1&&y2<=4&&!vis2[x2][y2])//如果1是选中的数2不越界3没走过
{
g++;//找到一个可走的点就加1
vis2[x2][y2] = 1;
Check_dfs(x2,y2);//搜寻下一个
}
}
return g;//返回连通个数
}
注：
本文思路来自网上大佬的启发，但是代码全是自己写的，组合数判重那里和数字转坐标思路是借鉴大佬的
大佬博客
全部代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int ans = 0;
int vis[20] = {
0};
int vis2[10][10]={
0};
int tmp[19];
int mp[6][6] = {
0};
int dx[4]={
0,1,0,-1};
int dy[4]={
-1,0,1,0};
int g = 0;
int Check_dfs(int x,int y)//判断连通
{
for(int i=0;i<4;i++)
{
int x2 = x + dx[i];
int y2 = y + dy[i];
//mp数组里为1，代表选出的5个数，即可走的数，看这5个数是否连通
if(mp[x2][y2]&&x2>=1&&x2<=3&&y2>=1&&y2<=4&&!vis2[x2][y2])//如果1是选中的数2不越界3没走过
{
g++;//找到一个可走的点就加1
vis2[x2][y2] = 1;
Check_dfs(x2,y2);//搜寻下一个
}
}
return g;//返回连通个数
}
int Check()//先进行坐标转换 ，
//这里非常简单，就是1234在第1行 ，5678第二行，9 10 11 12第3行
{
memset(mp,0,sizeof(mp));
int flag = 1;
int sx,sy;//记录起始点，必须从从这里出发，找到连通的5个数即可
for(int i=1;i<=5;i++)
{
if(tmp[i]>=1&&tmp[i]<=4) //如果1<=tmp[i]<=4 .那么肯定在第一行
{
mp[1][tmp[i]] = 1;
if(flag)
{
sx=1,sy=tmp[i],flag=0;
}
}
else if(tmp[i]>=5&&tmp[i]<=8)//如果5<=tmp[i]<=8 .那么肯定在第二行
{
mp[2][tmp[i]-4] = 4;
if(flag)
{
sx=2,sy=tmp[i]-4,flag=0;
}
}
else //如果9<=tmp[i]<=12 .那么肯定在第三行
{
mp[3][tmp[i]-8] = 1;
if(flag)
{
sx=3,sy=tmp[i]-8,flag=0;
}
}
}
g = 1;//从起始点出发，自然加个1
memset(vis2,0,sizeof(vis2));
vis2[sx][sy] = 1;
if(Check_dfs(sx,sy)==5) return 1;//如果是5个连通的数，则返回1
else return 0;
}
void dfs(int num)//选5个数
{
if(num==6)
{
if(Check()) ans++;//选了5个数，并且判断连通
return ;
}
for(int i=1;i<=12;i++)
{
if(!vis[i])
{
if(i>tmp[num-1]) //这里很关键，防止出现重复的组合数
{
vis[i] = 1;//数字i选过了
tmp[num] = i;// 把数字i存入 ，tmp数组中的第num-1个数
dfs(num+1);
vis[i] = 0;
}
}
}
}
int main()
{
dfs(1);
cout<<ans<<endl;
return 0;
}
京公网安备 11010502036488号