【四色地图】

【题目来自百度】 有形如下列图形的地图，图中每一块区域代表一个国家，现请你用红（1）、兰（2）、黄（3）、绿（4）四种颜色给这些国家填上颜色，要求每一国家用一种颜色，且任意两个相邻国家的颜色不能相同，请给出一种符合条件的填色方案。给出国家的数量（<=50）和它们的邻接关系。找出所有方案，按国家编号由小到大输出，并输出填色方案数。

输入
7
0 1 0 0 0 0 1
1 0 1 1 1 1 1
0 1 0 1 0 0 0
0 1 1 0 1 0 0
0 1 0 1 0 1 0
0 1 0 0 1 0 1
1 1 0 0 0 1 0

 输出
1 2 1 3 1 3 4

1

【AC代码】

#include<stdio.h> #define max 51 int map[max][max],p[max]={0}; int n,i,j,total=0; /** *map[i][j]记录接壤的情况 *p[i]记录第i个区域涂的颜色 */ void _solve(int x) {if(x>n){for(j = 1;j <= n;j++)printf("%d ",p[j]);printf("\n");total++;}else{for(j = 1;j <= 4;j++)//枚举四种颜色 {int flag=1;for(i = 1;i < x;i++){if(map[x][i] != 0 && p[i]==j)//若与已涂色的接壤区域同色 {flag=0;break;}}if(flag!=0){p[x]=j;//记录第x块区域为j色 _solve(x+1);p[x]=0;//回溯时归零 }}} } int main() {scanf("%d",&n);for(i = 1;i <= n;i++)for(j = 1;j <= n;j++)scanf("%d",&map[i][j]);_solve(1);printf("%d",total);return 0; }

总结

以上是生活随笔为你收集整理的【四色地图】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。