CSU 1508：地图的四着色（DFS+剪枝）

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1508

题意：地图中四联通的块是一个国家，A和B每个人可以涂两种颜色，且B不能涂超过5次，相邻的国家不能涂一样的颜色，并且最后每种颜色都要用上，问共有多少种涂色方案。

思路：先DFS处理出图中的国家，然后先用一个邻接矩阵存下相邻的国家（直接用邻接表会有重边），然后再用邻接表存图。数方案个数的时候，假设共有a，b，c，d这四种颜色，A可以涂a，b，B可以涂c，d。因为颜色之间没有差异，所以A先涂a颜色，B先涂c颜色，那么和A先涂b颜色，B先涂c或者d颜色是一样的。所以暂时假设A先涂a颜色，B先涂c颜色，然后利用平时判断二分图一样，去染色，记得染完色之后col[num]要置0。通过约束条件得到答案后，因为有先涂a-c，a-d，b-c，b-d这四种情况，所以最后答案*4。

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <cstdlib>

 #include <algorithm>

 #include <string>

 #include <iostream>

 #include <stack>

 #include <map>

 #include <queue>

 #include <set>

 using namespace std;

 typedef long long LL;

 #define N 40

 #define INF 0x3f3f3f3f

 struct node {

     int v, nxt;

 }edge[N*N*];

 int n, m, vis[N][N], tu[N][N], cnt, col[N], head[N], ans, tot, dx[] = {, -, , }, dy[] = {, , , -};

 char mp[N][N];

 bool check(int x, int y) { if( < x && x <= n &&  < y && y <= m) return true; return false; }

 void Add(int u, int v) { edge[tot].v = v; edge[tot].nxt = head[u]; head[u] = tot++; }

 void DFS(int x, int y, char c) {

     for(int i = ; i < ; i++) {

         int nx = dx[i] + x, ny = dy[i] + y;

         if(check(nx, ny) && !vis[nx][ny] && mp[nx][ny] == c) {

             vis[nx][ny] = cnt; DFS(nx, ny, c);

         }

     }

 }

 bool judge(int u, int c) {

     for(int i = head[u]; ~i; i = edge[i].nxt)

         if(col[edge[i].v] == c) return false;

     return true;

 }

 void dfs(int num, int a, int b, int c, int d) {

     if(num == cnt + ) {

         if(a && b && c && d) ans++;

         return ;

     }

     if(judge(num, )) {

         col[num] = ;

         dfs(num + , a + , b, c, d);

         col[num] = ;

     }

     if(a >  && judge(num, )) {

         col[num] = ;

         dfs(num + , a, b + , c, d);

         col[num] = ;

     }

     if(c + d <  && judge(num, )) {

         col[num] = ;

         dfs(num + , a, b, c + , d);

         col[num] = ;

     }

     if(c + d <  && c && judge(num, )) {

         col[num] = ;

         dfs(num + , a, b, c, d + );

         col[num] = ;

     }

 }

 int main()

 {

     int cas = ;

     while(~scanf("%d%d", &n, &m)) {

         for(int i = ; i <= n; i++) scanf("%s", mp[i] + );

         memset(head, -, sizeof(head));

         memset(vis, , sizeof(vis));

         memset(col, , sizeof(col));

         memset(tu, , sizeof(tu));

         tot = cnt = ans = ;

         for(int i = ; i <= n; i++)

             for(int j = ; j <= m; j++)

                 if(!vis[i][j]) { cnt++; vis[i][j] = cnt; DFS(i, j, mp[i][j]); }

         for(int i = ; i <= n; i++) {

             for(int j = ; j <= m; j++) {

                 if(vis[i-][j] && vis[i-][j] != vis[i][j]) tu[vis[i][j]][vis[i-][j]] = tu[vis[i-][j]][vis[i][j]] = ;

                 if(vis[i][j-] && vis[i][j-] != vis[i][j]) tu[vis[i][j-]][vis[i][j]] = tu[vis[i][j]][vis[i][j-]] = ;

             }

         }

         for(int i = ; i <= cnt; i++)

             for(int j = ; j <= cnt; j++)

                 if(i != j && tu[i][j]) Add(i, j);

         dfs(, , , , );

         printf("Case %d: %d\n", cas++, ans * );

     }

     return ;

 }

巴特西

CSU 1508：地图的四着色（DFS+剪枝）

最新文章

热门文章