蓝桥杯剪邮票（蒟蒻也能懂的题解）

文章目录

@[TOC]
题目
答案：116
思路：写得很暴力，代码多一点，但非常好懂
选出5个组合数——排列组合
数字转坐标
判断是否连通
注：
全部代码

题目

剪邮票【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;
}