题意：给定n*m的网格图，上面只有字符'.' 和 数字0-9。其中数字表示这是该格是古老的土地，字符'.'表示该格只是普通的土地。
可以认为一块古老的农田由四联通的所有数字相同的格组成的块，一块普通的农田只由一格组成。
现在要建立最大数目的农田，要求任意两块农田不能相邻。问你能够建立的最大数目。
n,m<=10
思路：把四联通的同一个数字缩成一个，每个字符.当做单独的一个，按照相邻四联通情况建图
这样建出来的图不一定是二分图，变成了一个一般图最大独立集问题
考虑一般图最大独立集=建反图后最大团大小，使用爆搜版本的最大团求解，随机化的最大团正确性在此题范围下没有保证，甚至连样例有时都过不去……
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair
#define N 210000
#define M 130
#define MOD 1000000007
#define eps 1e-8
#define pi acos(-1) const int dx[]={-,,,};
const int dy[]={,,-,}; char ch[M];
int num[M][M],a[M][M],set[M][M],f[M][M],g[M],p[M],ans; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} bool dfs(int size,int dep)
{
if(!size)
{
if(dep>ans)
{
ans=dep;
return ;
}
else return ;
}
for(int i=;i<=size;i++)
{
if(dep+size-i+<=ans) return ;
int u=set[dep][i];
if(dep+g[u]<=ans) return ;
int num=;
for(int j=i+;j<=size;j++)
if(f[u][set[dep][j]]) set[dep+][++num]=set[dep][j];
if(dfs(num,dep+)) return ;
}
return ;
} int main()
{
freopen("E.in","r",stdin);
freopen("E.out","w",stdout);
int cas,n,m,size,id;
scanf("%d",&cas);
for(int v=;v<=cas;v++)
{
scanf("%d%d",&n,&m);
for(int i=;i<=;i++) p[i]=;
id=;
for(int i=;i<=n;i++)
{
scanf("%s",ch+);
for(int j=;j<=m;j++)
{
if(''<=ch[j]&&ch[j]<='')
{
if(!p[ch[j]-'']) p[ch[j]-'']=++id;
num[i][j]=p[ch[j]-''];
}
else num[i][j]=++id;
}
} for(int i=;i<=id;i++)
for(int j=;j<=id;j++) f[i][j]=i!=j; for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
for(int k=;k<=;k++)
{
int x=i+dx[k];
int y=j+dy[k];
if(x<||x>n||y<||y>m) continue;
f[num[i][j]][num[x][y]]=;
f[num[x][y]][num[i][j]]=;
}
} ans=;
for(int i=id;i>;i--)
{
size=;
for(int j=i+;j<=id;j++)
if(f[i][j]) set[][++size]=j;
dfs(size,);
g[i]=ans;
}
printf("Case #%d: %d\n",v,ans);
}
return ;
}