题目原文
https://code.google.com/codejam/contest/32002/dashboard#s=p2
Problem

A local high school is going to hold a final exam in a big classroom. However, some students in this school are always trying to see each other's answer sheet during exams!

The classroom can be regarded as a rectangle of M rows by N columns of unit squares, where each unit square represents a seat.

The school principal decided to set the following rule to prevent cheating:
Assume a student is able to see his left, right, upper-left, and upper-right neighbors' answer sheets. The assignment of seats must guarantee that nobody's answer sheet can be seen by any other student.

As in this picture, it will not be a good idea to seat anyone in A, C, D, or E because the boy in the back row would be able to see their answer sheets. However, if there is a girl sitting in B, he will not be able to see her answer sheet.

Some seats in the classroom are broken, and we cannot put a student in a broken seat.

The principal asked you to answer the following question: What is the maximum number of students that can be placed in the classroom so that no one can cheat?

Input

The first line of input gives the number of cases, C. C test cases follow. Each case consists of two parts.

The first part is a single line with two integers M and N: The height and width of the rectangular classroom.

The second part will be exactly M lines, with exactly N characters in each of these lines. Each character is either a '.' (the seat is not broken) or 'x' (the seat is broken, lowercase x).

Output

For each test case, output one line containing "Case #X: Y", where X is the case number, starting from 1, and Y is the maximum possible number of students that can take the exam in the classroom.

Limits

C = 20

Small dataset

1 ≤ M ≤ 10
1 ≤ N ≤ 10

Large dataset

1 ≤ M ≤ 80
1 ≤ N ≤ 80

Sample

Input

Output

4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....

Case #1: 4
Case #2: 1
Case #3: 2

图的最大独立集：
#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXM=85,MAXN=85;
const int MAXV=MAXN*MAXM;
 
char seat[MAXM][MAXN+1];
const int dx[]={-1,-1,1,1};
const int dy[]={-1,0,-1,0};
int M,N,V;

vector<int>G[MAXV];
int match[MAXV];
bool used[MAXV];

void add_edge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);  
} 

bool dfs(int v)
{
    used[v]=true;
    for(int i=0;i<G[v].size();i++){
        int u=G[v][i],w=match[u];
        if(w<0 || !used[w] && dfs(w)){
            match[u]=v;
            match[v]=u;
            return true; 
        } 
    }
    return false;
}

int bipartite_matching()
{
    int num=0;
    memset(match,-1,sizeof(match));
    for(int v=0;v<V;v++){
        if(match[v]<0){
            memset(used,0,sizeof(used));
            if(dfs(v)) num++;
        }
    }
    return num;
}

int main(void)
{
    freopen("input.txt","r",stdin);
    int t,kase;
    scanf("%d",&t);
    while(t--)
    {
        kase++;
        scanf("%d%d",&M,&N);
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++)
                cin>>seat[i][j];
        }
        int num=0;
        V=M*N;
        
        for(int y=0;y<M;y++){
            for(int x=0;x<N;x++){
                if(seat[y][x]=='.'){
                    num++;
                    for(int k=0;k<4;k++){
                        int x2=x+dx[k];
                        int y2=y+dy[k];
                        if(0<=x2 && x2<N && 0<=y2 && y2<M && seat[y2][x2]=='.'){
                            add_edge(y*M+x,y2*M*x2);
                        }
                    }
                }
            } 
        } 
        printf("Case #%d:%d\n",kase,num-bipartite_matching());
        for(int v=0;v<V;v++) G[v].resize(0);
    }
    return 0;   
}