CSU_1508_地图的四着色

 地图的四着色

Time Limit: 20 Sec   Memory Limit: 128 MB

Submit: 66   Solved: 35

[ 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      

HINT

首先建图，注意如果直接用邻接表的话要判重

所以先用邻接矩阵，然后再转成邻接表（因为显然是稀疏图）

之后dfs给地图上色就好了

这里注意这个问题容易超时

然后其实对于第一个国家的涂色可以只分男人和女人涂，然后把结果乘二就可以了

#include <iostream>
//#include<bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
 
const int MT=22;
char ti[MT][MT];
int ti2[MT][MT];   //转化成一个国家对应一个数字
 
const int M=32;
int g[M][M];       //邻接矩阵
int gg[M][M];      //邻接表
int col[M];
int isu[5];
 
queue<int > re;
 
int ans;
 
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
 
void bfs(int stx,int sty,int na)    //转化成一个国家一个数字
{
    while(!re.empty())
        re.pop();
    ti2[stx][sty]=na;
    re.push(stx+MT*sty);
    while(!re.empty())
    {
        int t=re.front();
        re.pop();
        int tx=t%MT,ty=t/MT;
        for(int i=0;i<4;i++)
        {
            int x=tx+dx[i],y=ty+dy[i];
            if(!ti2[x][y]&&ti[stx][sty]==ti[x][y])
            {
                ti2[x][y]=na;
                re.push(x+MT*y);
            }
        }
    }
}
 
//void dfs_g(int stx,int sty,int na)
//{
//    ti2[stx][sty]=na;
//    for(int i=0;i<4;i++)
//    {
//        int x=stx+dx[i],y=sty+dy[i];
//        if(!ti2[x][y]&&ti[stx][sty]==ti[x][y])
//        {
//            ti2[x][y]=na;
//            dfs_g(x,y,na);
//        }
//    }
//}
 
void dfs(int now,int na,int nn)       //涂色，now是现在涂第几个国家，na是一共有多少国家，nn女人涂了几个国家
{
    if(nn>5)
        return;
    if(now==na)
    {
 
        if(isu[1]+isu[2]+isu[3]+isu[4]==4)
        {
            ans++;
//            for(int i=1;i<na;i++)
//                cout<<col[i]<<" ";
//            cout<<endl;
        }
        return;
    }
    for(int i=1;i<=4;i++)
    {
        if(i==3&&nn==5)       //这个剪枝非常重要，提前把这种不成立的情况去掉可以少太多的判断和搜索
            return;
        int f=1;
        for(int j=1;j<=gg[now][0];j++)
        {
            if(i==col[gg[now][j]])
            {
                f=0;
                break;
            }
        }
        if(f)
        {
            int chan=0;
            if(i==1||i==2)
            {
                col[now]=i;
                if(!isu[i])
                {
                    isu[i]=1;
                    chan=i;
                }
                dfs(now+1,na,nn);
                col[now]=0;
                if(chan)
                    isu[chan]=0;
            }
            else
            {
                col[now]=i;
                if(!isu[i])
                {
                    isu[i]=1;
                    chan=i;
                }
                dfs(now+1,na,nn+1);
                col[now]=0;
                if(chan)
                    isu[chan]=0;
            }
        }
    }
}
 
int main()
{
    int n,m;
    //double cl = clock();
    //freopen("f.in","r",stdin);
    int ca=1;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        ans=0;
        int na=1;
        memset(ti,0,sizeof(ti));
        memset(ti2,0,sizeof(ti2));
        memset(g,0,sizeof(g));
        memset(gg,0,sizeof(gg));
//        for(int i=1;i<M;i++)
//            gg[i][0]=0;
        for(int i=1;i<=n;i++)
            scanf("%s",ti[i]+1);
 
        for(int i=1;i<=n;i++)  //转化为1片一个数
        for(int j=1;j<=m;j++)
        {
            if(!ti2[i][j])
                bfs(i,j,na++);
        }
 
        for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
        {
            if(ti2[i][j]!=ti2[i][j+1])
            {
                int t1=ti2[i][j],t2=ti2[i][j+1];
                g[t1][t2]=g[t2][t1]=1;
            }
        }
        for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
        {
            if(ti2[i][j]!=ti2[i+1][j])
            {
                int t1=ti2[i][j],t2=ti2[i+1][j];
                g[t1][t2]=g[t2][t1]=1;
            }
        }
        for(int i=1;i<na;i++)   //矩阵转表
        {
             for(int j=1;j<i;j++)
            {
                if(g[i][j])
                {
                    gg[i][++gg[i][0]]=j;
                    gg[j][++gg[j][0]]=i;
                }
            }
        }
 
//        for(int i=1;i<na;i++)
//        {
//            for(int j=1;j<=gg[i][0];j++)
//            {
//                cout<<i<<" "<<gg[i][j]<<endl;
//            }
//        }
//        cout<<na<<endl;
        //建图如上
 
        col[1]=1;isu[1]=1;isu[2]=isu[3]=isu[4]=0;
        dfs(2,na,0);
        col[1]=3;isu[3]=1;isu[1]=isu[2]=isu[4]=0;
        dfs(2,na,1);
 
        printf("Case %d: %d\n",ca++,ans<<1);
    }
//    cl = clock() - cl;
//    fprintf(stderr,"Run Time = %lf\n",cl/CLOCKS_PER_SEC);
    return 0;
}