1116四色问题

先附上题目 传送门

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

8 0 0 0 1 0 0 1 0  0 0 0 0 0 1 0 1  0 0 0 0 0 0 1 0  1 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0  0 1 0 0 0 0 0 0  1 0 1 0 0 0 0 0  0 1 0 0 0 0 0 0

样例输出 Sample Output

15552

数据范围及提示 Data Size & Hint

n<=8

一道简单的深搜 思路：

对于当前的点，我们枚举4种颜色，判定它是否与其他任意一点相邻并且颜色一样，如果一样退出本层，如果与

其他所有的点都不相邻或颜色不一样，将颜色标记并搜索下一个点。当当前的点大于N时，方案数加一（如果等

于时加一，相当于最后一个点未展开）

代码如下

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int num[10][10],col[10];//num存连接关系，col存颜色 int n,tot=0;//tot存方案数 void dfs(int a) { int i,j; if(a>n) { tot++; return; } else { for(j=1;j<=4;j++) { for(i=1;i<=a;i++) { if(num[a][i]==1&&col[i]==j) { break; } else if(i==a) { col[a]=j; dfs(a+1); col[a]=0; } } } } } int main() { int i,j; scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&num[i][j]); } } dfs(1); printf("%d",tot); }