剪邮票

2018-01-27 10:26:51来源:网络收集作者:咖啡不加糖人点击

分享


剪邮票

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


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



剪邮票剪邮票剪邮票

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


#include
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()
{
sets;
s.insert(a[0]);
set::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<}
第二种思路:

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


#include
using namespace std;
typedef long long ll;
int a[5];
int ans = 0;
set > 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 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<}



相关文章

    无相关信息

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台