失恋巧克力职人
Description
纱绘子喜欢巧克力,尤其喜欢巴黎“幸福工坊”的巧克力。
爽太为了追求深爱的纱绘子,远赴巴黎“幸福工坊”见习,梦想着有朝一日能回到日本开一间巧克力店,做出纱绘子最爱的巧克力——这样,纱绘子就一定会每天都来光顾吧!那么每天都能见到纱绘子了吧!
爽太的梦想实现了——他开了自己的巧克力店“choco la vie”,将记忆里纱绘子的口味与巴黎的技艺相结合,设计出了以bonbon巧克力、糖渍橙皮巧克力为代表的四种巧克力。纱绘子也如愿每日笑着前来:“每天都能吃到这样的巧克力,真是太幸福了!”
爽太每天都要将新鲜出炉的巧克力在柜台上固定的一些位置摆放满。为了给纱绘子带来新鲜感,他希望每天巧克力的布置都不一样,并且两个相同种类的巧克力不能相邻摆放——“不然就太无聊了!”他想知道,一共有几种布置巧克力的方案。
这里要注意的是,柜台能放巧克力的位置虽然固定,但却不是规则分布的。因此我们会将相邻的位置一对对地给出。
Input (From File: colour.in)
第一行两个数N和M,表示放巧克力的位置的个数和相邻的位置的对数。
接下来M行,每行一组数A,B表示A,B相邻。
Output (To File: colour.out)
一个数,表示巧克力布置的方法数。
Sample Input 1
5 4
1 2
1 3
1 4
1 5
Sample Output 1
324
Hint
40%的数据N <=5
100%的数据N <= 10, M <= 50
方法:这题其实是一个简单DFS(深搜),感谢霍普克洛夫特特与罗伯特•塔扬,发明了深搜。算了,不说题外话了。这题的主要思路先用数组连接每个相邻的巧克力格,再是搜索每个巧克力格。在放入巧克力前,我们要与前面有放过巧克力的格子进行比较,如果巧克力有相连的关系,并且自己格子准备放的巧克力和相连的格子里已经放的巧克力一样的话,就不放这种巧克力。并将巧克力放满了后统计次数,最后输出。
Ok,要讲的都讲了,让我们用热烈的掌声欢迎这题的——代码!
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
bool p[20][20];
int a[20];
int math(int x,int t) //判断放置是否合法
{
for(int i=1;i<x;i++)
if(p[x][i]==1&&a[i]==t)
return 0;
return 1;
}
void fun(int x) //深搜标准模板之一
{
if(x>n)
{
ans++;
return ;
}
for(int i=1;i<=4;i++)
if(math(x,i)==1)
{
a[x]=i;
fun(x+1);
a[x]=0;
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
p[x][y]=p[y][x]=1; //用数组证明这两个巧克力格是有相连的,类似图
}
fun(1);//DFS
cout<<ans;
return 0;
}//本文仅供产考,抄袭套作遭雷劈!!!