首页 » C语言 » 剪邮票

剪邮票

原文 http://blog.csdn.net/Soul_97/article/details/79170385

2018-01-27 02:00:45阅读(168)

邮票


如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。

请你计算,一共有多少种不同的剪取方法。

剪邮票剪邮票剪邮票

思路:每生成一张邮票之后加入到集合种,然后再判断后面加入的邮票是不是和它相邻,每次都要更新集合中的元素,这种思想类似于普里姆生成最小树的算法,可以参考那个思想看代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5];
int ans = 0;
bool judge(int x,int y)
{
	if(x > y) swap(x,y);
	if(y - x == 4 || y == x +1 && x % 4 != 0)
	return true;
	
	return false;
}
bool connected()
{
	set<int>s;
	s.insert(a[0]);
	set<int>::iterator iter;
	for(int i = 1;i <= 4;i ++)
	{
		for(int j = 1;j < 5;j ++)
		for(iter = s.begin();iter != s.end();iter ++) 
		if(judge(*iter,a[j])) s.insert(a[j]);
	}
	
	return s.size() == 5;
}
void dfs(int x,int pre)
{
	if(x == 5)
	{
		if(connected()) ans ++;
		return ;
	}
	
	for(int i = pre+1;i <= 12;i ++)
	{
		a[x] = i;
		dfs(x+1,i);
	}
}
int main()
{
	dfs(0,0);
	cout<<ans<<endl;
}

第二种思路:

枚举第1张、第2张……第5张邮票,保证第i张与之前i-1张中至少一张相连。最后需要去重

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5];
int ans = 0;
set<set<int> > ss;
bool used[13] = {false};
bool judge(int x,int y)
{
	if(x > y) swap(x,y);
	if(y - x == 4 || y == x +1 && x % 4 != 0)
	return true;
	
	return false;
}
bool ok(int x,int i)
{
	if(x == 0)
		return true;
	
	for(int j = 0;j < x;j ++)
	if(judge(a[j],i))
	return true;
	
	return false;
}
void dfs(int x)
{
	if(x == 5)
	{
		set<int> s(a,a+5);
		ss.insert(s);
		return ; 
	}
	
	for(int i = 1;i <= 12;i ++)
	{
		if(!used[i] && ok(x,i))
		{
			used[i] = true;
			a[x] = i;
			dfs(x + 1);
			used[i] = false;
		}
	}
}
int main()
{
	dfs(0);
	cout<<ss.size()<<endl;
}



最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹