题目链接：hdu5556-Land of Farms

题意：
​ 给定一个图，图上的数字表示ancient farms，' . '表示新农场，要求在这片土地上建立农场，农场之间不能有连接（Manhattan distance is exactly 1），问最多能修建多少个农场。
题解：
​ 由题可知，只需要建图，然后求图的最大独立集，及求其补图的最大团。
参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,id,ans;
int mp[15][15],dx[5],dy[5];
int cnt[105],used[105];
bool edge[105][105];
char farm[15][15];
//给原图染色
void col(int x,int y,char cc)
{
    if(x<1||x>n||y<1||y>m||farm[x][y]!=cc||mp[x][y]!=-1)
        return;
    mp[x][y]=id;
    for(int i=1;    i<=4;   i++)
        col(x+dx[i],y+dy[i],cc);
}
void color()
{
    id=0;
    memset(mp,-1,sizeof(mp));
    for(int i=1;    i<=n;   i++)
    {
        for(int j=1;    j<=m;   j++)
        {
            if(farm[i][j]=='.')
            {
                mp[i][j]=id;
                id++;
            }
            else if(mp[i][j]==-1)
            {
                col(i,j,farm[i][j]);
                id++;
            }
        }
    }
}
//建新图
void newgraph(int x1,int y1,int x2,int y2)
{
    if(x2<1||x2>n||y2<1||y2>m)
        return;
    int x=mp[x1][y1];
    int y=mp[x2][y2];
    if(x==y)
        return;
    edge[x][y]=edge[y][x]=1;
}
void buildgraph()
{
    memset(edge,0,sizeof(edge));
    for(int i=1;    i<=n;   i++)
        for(int j=1;    j<=m;   j++)
            for(int k=1;    k<=4;   k++)
                newgraph(i,j,i+dx[k],j+dy[k]);
}
//跑补图的最大团
bool dfs(int u,int dep)
{
    for(int i=u+1;  i<id;   i++)
    {
        if(cnt[i]+dep<=ans)
            return 0;
        if(edge[u][i])
        {
            int j=0;
            for(j=0;    j<dep;  j++)
            {
                if(!edge[i][used[j]])
                    break;
            }
            if(j==dep)
            {
                used[dep]=i;
                if(dfs(i,dep+1))
                    return 1;
            }
        }
    }
    if(dep>ans)
    {
        ans=dep;
        return 1;
    }
    return 0;
}
void maxclique()
{
    memset(used,0,sizeof(used));
    memset(cnt,0,sizeof(cnt));
    for(int i=id-1;    i>=0;   i--)
    {
        used[0]=i;
        dfs(i,1);
        cnt[i]=ans;
    }
}
int main()
{
    scanf("%d",&T);
    dx[1]=1;    dx[2]=-1;   dx[3]=0;    dx[4]=0;
    dy[1]=0;    dy[2]=0;    dy[3]=-1;   dy[4]=1;
    int icase=0;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;    i<=n;   i++)
            scanf("%s",farm[i]+1);
        color();
        buildgraph();
        //构造补图
        for(int i=0;    i<id;   i++)
            for(int j=0;    j<id;   j++)
                if(i==j)
                    edge[i][j]=0;
                else
                    edge[i][j]^=1;
        ans=0;
        maxclique();
        printf("Case #%d: %d\n",++icase,ans);
    }
    return 0;
}