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

本文链接：https://blog.csdn.net/acm_cxq/article/details/52224876

该博客介绍了如何使用BFS和DFS解决一个四连通地图的着色问题，旨在使相邻区域颜色不同。题目中限制了最多5个国家由女朋友涂色（蓝黄两色），并要求每种颜色至少使用一次。博客提供了输入输出格式及样例，主要针对ACM竞赛中的问题进行探讨。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

地图的四着色 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;
}