csu 1508 地图的四着色（BFS,DFS,巧妙剪枝）

地图的四着色 Time Limit: 20 Sec   Memory Limit: 128 MB Submit: 105   Solved: 48 [ Submit][ Status][ Web Board]

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

Case 1: 24 Case 2: 144 Case 3: 3776 题意：相同字母连在一起的是一个国家，输入保证不超过30个国家，现在要用四种颜色给这些国家染色，要求相邻的国家不能颜色相同，问一共有多少种方法 男的只能染两种，女的两种，女的最多染五次 思路：看到网上有二分图的解法，晚点再去看看好了。 这里第一遍BFS先把国家编一个号，然后再跑一遍BFS求出国家与国家之间的相邻关系，是一个邻接矩阵 为了加速我们用邻接表来存，这样每次找到一个节点的时候找与其相邻的国家就会很容易。 然后用DFS跑一边，注意不能盲目跑，会TLE。 我们可以强行让男的第一次先涂第一种颜色，女的第一次先涂第三种颜色。（对于此题，先涂哪一个颜色都是等价的，所以结果是2*2倍）这样求出来的ans是最后ans的1/4 可以加速很多。 代码: #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> using namespace std; int n,m,cnt; int vis[25][25]; long long ans; char s[25][25]; int dir[4][2]= {-1,0,0,-1,1,0,0,1}; int ma[35][35],flag[35][35]; int color[35]; struct Node { int x,y; }; struct Edge { int v,next; } edge[2000]; int head[35],num; void addedge(int u,int v) { edge[num].v=v; edge[num].next=head[u]; head[u]=num++; } void bfs(int x,int y) { cnt++; queue<Node>que; Node a,next; a.x=x,a.y=y; que.push(a); while(!que.empty()) { Node now=que.front(); que.pop(); vis[now.x][now.y]=cnt; for(int i=0; i<4; i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; if(next.x<0||next.y<0||next.x>=n||next.y>=m||vis[next.x][next.y]||s[next.x][next.y]!=s[x][y]) continue; que.push(next); } } } void bfs1(int x,int y) { queue<Node>que; Node a,next; a.x=x,a.y=y; que.push(a); while(!que.empty()) { Node now=que.front(); que.pop(); flag[now.x][now.y]=1; for(int i=0; i<4; i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; if(next.x<0||next.y<0||next.x>=n||next.y>=m) continue; if(vis[next.x][next.y]!=vis[x][y]) { ma[vis[x][y]][vis[next.x][next.y]]=ma[vis[next.x][next.y]][vis[x][y]]=1; continue; } if(flag[next.x][next.y]) continue; que.push(next); } } } void init() { ans=cnt=0; memset(vis,0,sizeof(vis)); for(int i=0; i<n; i++) for(int j=0; j<m; j++) if(!vis[i][j]) bfs(i,j); memset(ma,0,sizeof(ma)); memset(flag,0,sizeof(flag)); for(int i=0; i<n; i++) for(int j=0; j<m; j++) if(!flag[i][j]) bfs1(i,j); memset(head,-1,sizeof(head)); num=0; for(int i=1; i<=cnt; i++) for(int j=1; j<i; j++) if(ma[i][j]) addedge(i,j); } int check(int pos,int k) { for(int i=head[pos]; i!=-1; i=edge[i].next) if(color[edge[i].v]==k) return 0; return 1; } void dfs(int pos,int a0,int a1,int a2,int a3)///涂到第几个城市，四种颜色分别涂了几个 { if(pos==cnt+1) { if(a0&&a1&&a2&&a3) ans++; return; } color[pos]=0; if(check(pos,0)) dfs(pos+1,a0+1,a1,a2,a3); color[pos]=1; if(a0&&check(pos,1)) dfs(pos+1,a0,a1+1,a2,a3); color[pos]=2; if(a2+a3<5&&check(pos,2)) dfs(pos+1,a0,a1,a2+1,a3); color[pos]=3; if(a2&&a2+a3<5&&check(pos,3)) dfs(pos+1,a0,a1,a2,a3+1); } int main() { int cas=1; while(~scanf("%d %d",&n,&m)) { for(int i=0; i<n; i++) scanf("%s",s[i]); init(); ans=0; dfs(1,0,0,0,0); printf("Case %d: %lld\n",cas++,4*ans); } return 0; }