1116 四色问题
时间限制: 1 s空间限制: 128000 KB题目等级 : 黄金 Gold题解题目描述Description
给定N（小于等于8）个点的地图，以及地图上各点的相邻关系，请输出用4种颜色将地图涂色的所有方案数（要求相邻两点不能涂成相同的颜色）
数据中0代表不相邻，1代表相邻
输入描述Input Description
第一行一个整数n，代表地图上有n个点
接下来n行，每行n个整数，每个整数是0或者1。第i行第j列的值代表了第i个点和第j个点之间是相邻的还是不相邻，相邻就是1，不相邻就是0.
我们保证a[i][j] = a[j][i] （a[i,j] = a[j,i]）
输出描述Output Description
染色的方案数
样例输入Sample Input
80 0 0 1 0 0 1 00 0 0 0 0 1 0 10 0 0 0 0 0 1 01 0 0 0 0 0 0 00 0 0 0 0 0 0 00 1 0 0 0 0 0 01 0 1 0 0 0 0 00 1 0 0 0 0 0 0
样例输出Sample Output
15552
数据范围及提示Data Size & Hint
n<=8
1 #include<iostream> 2 3 #include<cstdlib> 4 5 #include<cstdio> 6 7 #include<cstring> 8 9 #include<cmath>10 11 #include<algorithm>12 13 using namespace std;14 15 int n,lin[10][10],color[10],ans=0;16 17 void dfs(int point,int col)18 19 //point点所代表的颜色 20 21 {22 23 if(point==n+1)//如果所有点都有颜色了 24 25 {26 27 for(int i=1;i<=n;i++)28 29 {30 31 for(int j=1;j<=n;j++)32 33 {34 35 if(lin[i][j]==1&&color[i]==color[j])//判断相邻的是否是相同的颜色 36 37 return;38 39 }40 41 }42 43 ans++;//如果全部符合 44 45 return;46 47 }48 49 color[point]=col;50 51 for(int i=1;i<=4;i++)52 53 {54 55 dfs(point+1,i);//深搜下一个点所代表的颜色 56 57 }58 59 return;60 61 }62 63 int main()64 65 {66 67 scanf("%d",&n);68 69 for(int i=1;i<=n;i++)70 71 for(int j=1;j<=n;j++)72 73 scanf("%d",&lin[i][j]);74 75 dfs(1,1);76 77 cout<<ans;78 79 return 0;80 81 }
躲在某一时间想念一段时光的掌纹，
