题目大意：
一个N*M的矩阵，其中“.”代表空地，“0-9”代表古代建筑，我们如果选择了一个编号的古代建筑想要建立，那么对应就要将全部该编号的建筑建立起来，如果在空地上建筑，只建立当前点。问最多能够建立多少种建筑，并且每两种建筑之间没有公共边。
题目意识比较难懂，我们来分析一下第一组样例：
..3.
023.
.211 对应可以建出来这样的效果：
.X.Y
0...
..11 那么对应有4种建筑，输出4.
思路：
1、首先如果我们没有这些古代建筑，只是一个N*M的一个矩阵的话，我们按照点的坐标的奇偶性（（x+y）%2）将矩阵分成一个二分图，然后将每个点与其周围四个点（有公共边）建立一条无向边，表示这两个点如果在一起建立是矛盾的。
那么不难理解：我们现在跑一遍匈牙利算法求得的最大二分匹配数==最小点覆盖数*2（因为是无向边）.那么如果我们将属于最小点覆盖集的点去掉，剩下的点就是属于最大独立集的点，那么此时能够建立的最多的建筑的数目：n*m-最大匹配数/2【最大独立集=n-最大二分匹配数】
2、那么现在引入这些古代建筑，题干中保证了这些古代建筑一共只有10种（0-9），那么我们可以暴力枚举一下哪些古代建筑我们建立起来，哪些古代建筑我们不建立。对应建立起来的古代建组周围的“.”的点我们抛弃掉，建立起来的古代建筑的点也抛弃掉，没有建立起来的古代建筑的点也抛弃掉。剩下的“.”，我们按照第一步的思路建二分图，然后求最大独立集即可。
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define N 105
char s[N][N];
vector<pii> v[11];
int vis[10], nxt[4][2]={0, 1, 0, -1, 1, 0, -1, 0};
bool book[12][12];
int mp[12][12];
struct Max_Match
{int n;vector<int> g[N];bool vis[N];int left[N];void init(int n){this -> n = n;for(int i = 0; i <= n; i++)g[i].clear();memset(left, -1, sizeof(left));}bool match(int u){for(int i = 0; i < g[u].size(); i++){int v = g[u][i];if(!vis[v]){vis[v] = true;if(left[v] == -1 || match(left[v])){left[v] = u;return true;}}}return false;}int solve(){int ans = 0;for(int i = 1; i <= n; i++){memset(vis, false, sizeof(vis));if(match(i))ans++;}return ans;}
}MM;
int main()
{int T, n, m, kase=0;scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);for(int i=1; i<=n; i++) scanf("%s", s[i]+1);for(int i=0; i<=10; i++) v[i].clear();memset(vis, 0, sizeof(vis));int cnt=0;for(int i=1; i<=n; i++)for(int j=1; j<=m; j++){if(s[i][j]>='0'&&s[i][j]<='9'){if(!vis[s[i][j]-'0'])vis[s[i][j]-'0']=++cnt;v[vis[s[i][j]-'0']].push_back(pii(i, j));}}int stu=(1<<cnt)-1, cou, ans=0;for(int i=0; i<=stu; i++){cou=0;memset(book, false, sizeof(book));for(int j=0; j<cnt; j++){if((i>>j)&1){cou++;for(int k=0; k<v[j+1].size(); k++){int x=v[j+1][k].first;int y=v[j+1][k].second;book[x][y]=true;for(int ii=0; ii<4; ii++){int nx=x+nxt[ii][0];int ny=y+nxt[ii][1];if(nx<1||nx>n||ny<1||ny>m) continue;if(s[nx][ny]=='.') book[nx][ny]=true;}}}else{for(int k=0; k<v[j+1].size(); k++){int x=v[j+1][k].first;int y=v[j+1][k].second;book[x][y]=true;}}}bool flag=false;for(int j=0; j<cnt; j++){if((i>>j)&1){for(int k=0; k<v[j+1].size(); k++){int x=v[j+1][k].first;int y=v[j+1][k].second;for(int ii=0; ii<4; ii++){int nx=x+nxt[ii][0];int ny=y+nxt[ii][1];if(nx<1||nx>n||ny<1||ny>m) continue;if(s[nx][ny]=='.') continue;int t=vis[s[nx][ny]-'0'];if((i>>(t-1))&1){if(vis[s[nx][ny]-'0']==vis[s[x][y]-'0']) continue;flag=true;}}}}}if(flag) continue;int cnt=0;memset(mp, 0, sizeof(mp));for(int r=1; r<=n; r++)for(int c=1; c<=m; c++){if(s[r][c]=='.'&&!book[r][c])mp[r][c]=++cnt;}MM.init(cnt);for(int r=1; r<=n; r++)for(int c=1; c<=m; c++)if(s[r][c]=='.'&&!book[r][c]){for(int k=0; k<4; k++){int nx=r+nxt[k][0];int ny=c+nxt[k][1];if(nx<1||nx>n||ny<1||ny>m) continue;if(s[nx][ny]=='.'&&!book[nx][ny]){MM.g[mp[r][c]].push_back(mp[nx][ny]);}}}for(int r=1; r<=n; r++)for(int c=1; c<=m; c++)if(s[r][c]=='.'&&!book[r][c]){for(int k=0; k<4; k++){int nx=r+nxt[k][0];int ny=c+nxt[k][1];if(nx<1||nx>n||ny<1||ny>m) continue;if(s[nx][ny]=='.'&&!book[nx][ny]){MM.g[mp[r][c]].push_back(mp[nx][ny]);}if(s[nx][ny]!='.'){int tmp=vis[s[nx][ny]-'0']-1;if((i>>tmp)&1) continue;MM.g[mp[r][c]].push_back(mp[nx][ny]);}}}int tmp=cnt-MM.solve()/2;ans=max(ans, tmp+cou);}printf("Case #%d: %d\n", ++kase, ans);}return 0;
}