描述

有一个R行C列的网格地图，每个国家是一个四连通区域。你的任务是用红，绿，蓝，黄四种颜色给地图着色，使得相邻国家的颜色不同。
一个人着色比较无趣，所以你想请女朋友陪你一起涂——你涂红绿，她涂蓝黄。当然，绅士是不会让让女朋友受累的，所以她最多只需涂5个国家（恰好5个也行）。
你的任务是统计有多少种着色的方法。注意，每个颜色都至少要用一次。

输入

输入包含不超过100组数据。每组数据第一行为两个整数R和C (1<=R,C<=20)，即网格的行数和列数。以下R行每行C个大写字母。相同字母所组成的四连通区域代表一个国家。输入保证国家数目不超过30，并且大多数测试点的国家数都比较小。

输出

对于每组数据，输出测试点编号和着色方案数。

样例输入

2 4
AABB
BBAA
1 5
ABABA
4 7
AABAABB
ABBCCCB
BBAACBB
CCABBAC

样例输出

Case 1: 24
Case 2: 144
Case 3: 3776

思路：

以样例一为例

首先将给出的字符数组寻找连通块，将每个四连通的相同字母的每一块进行标号

即：AABB 转变为 ：0011
       BBAA                 2233

然后进行缩点，将每一块编号相同的区域作为以这个编号的结点，构建邻接矩阵，即如果一个编号的四连通区域有其他编号，就说明这两个点连通

即有：0110
           1001
           1001
           0110

此时有了邻接矩阵后，可以直接搜索进行染色以统计方案数，但由于数据范围过大因此会超时，考虑剪枝

假设男性使用 A、B 两个颜色涂色，女性使用 C、D 两个颜色涂色，此时男性、女性的涂色顺序有四种：AB|CD、AB|DC、BA|CD、BA|DC

由于无论哪个颜色先涂，结果最终都是等价的，因此规定男性使用的第一个颜色是 A，女性使用的第一个颜色是 C，然后进行搜索，最终求出来的 res 是结果的 1/4，因此最终答案为 res*4

源程序

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 2000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std; int n,m; char mp[N][N];//字符矩阵 int grade[N][N];//连通块标号 int G[N][N];//邻接矩阵 int colors[N]; void dfs(int x,int y,int num){//寻找连通块记录标号grade[x][y]=num;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx<0||nx>=n||ny<0||ny>=m)continue;if(mp[x][y]==mp[nx][ny]&grade[nx][ny]==-1)dfs(nx,ny,num);} } void buildMap(int num){//建立邻接矩阵for(int x=0;x<m;x++){for(int y=0;y<num;y++){for(int k=0;k<4;k++){int nx=x+dx[k];int ny=y+dy[k];if(nx<0||ny<0||nx>=num||ny>=num)continue;if(grade[x][y]!=grade[nx][ny]){int nodeX=grade[x][y];int nodeY=grade[nx][ny];G[nodeX][nodeY]=1;G[nodeY][nodeX]=1;}}}} } bool judge(int step,int color,int num){for(int i=0;i<num;i++)if(G[step][i]==1&&colors[i]==color)return false;return true; } int dye(int step,int A,int B,int C,int D,int num){//染色int res=0;if(step==num){if(A!=0&&B!=0&&C!=0&&D!=0)res++;return res;}if(judge(step,0,num)){colors[step]=0;res+=dye(step+1,A+1,B,C,D,num);}if(A&&judge(step,1,num)){colors[step]=1;res+=dye(step+1,A,B+1,C,D,num);}if(C+D<5&&judge(step,2,num)){colors[step]=2;res+=dye(step+1,A,B,C+1,D,num);}if(C&&C+D<5&&judge(step,3,num)){colors[step]=3;res+=dye(step+1,A,B,C,D+1,num);}colors[step]=-1;return res; } int main(){int Case=1;while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++){getchar();for(int j=0;j<m;j++)scanf("%c",&mp[i][j]);}//寻找连通块，并进行标号memset(grade,-1,sizeof(grade));int num=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grade[i][j]==-1){dfs(i,j,num++);}}}//建立邻接矩阵memset(G,0,sizeof(G));buildMap(num);//染色memset(colors,-1,sizeof(colors));int res=dye(0,0,0,0,0,num);printf("Case %d: %d\n",Case++,res*4);}return 0; }

 

总结

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

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