平面域着色

10304 平面域着色
时间限制:1000MS 内存限制:65535K 提交次数:188 通过次数:53
语言: not limited
描述
平面上有一点P，它是n个域D1、D2、……，Dn的共同交点，
现取k种颜色对这n个域进行着色，要求相邻两个域着的颜色不同，求着色方案数。
这里，2<=n<=10，1<=k<=9。
输入格式
输入：输入两个值：n和k。n为域的个数，k为颜色数
输出格式
输出：对n个域着色的方案数
如输入3 3
输出6
若不存在可能的着色方案，输出0。
输入样例
9
4 3
输出样例
18

10

------------------------------------------------------------

10304平面域着色（递归、分治）

#include<stdio.h>

#include"malloc.h"

intF(intm,intn)

{

if(m==3)returnn-2;

elseif(m==4)return(n-1)+(n-2)*(n-2);

else

return(n-1)*F(m-2,n)+(n-2)*F(m-1,n);

return0;

}

intmain()

{

intm,n,sum;

{

scanf("%d%d",&m,&n);

}while(m<0||n<0);

if(m==0||n==0)sum=0;

if(m==1)sum=n;

if(m>1)

{

if(n==1)sum=0;

if(n==2)

{

if(m%2==0)sum=2;

if(m%2==1)sum=0;

}

if(n>2)

{

if(m==2)

sum=n*(n-1);

if(m>=3)

sum=n*(n-1)*F(m,n);

}

}

printf("%d\n",sum);

return0;

}