#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <queue>#include <stack>#include <cmath>#include <algorithm>#define LL long long#define FOR(i, x, y) for(int i=x;i<=y;i++)using namespace std;const int MAXN = 600 + 10;int G[MAXN][MAXN];int vis[MAXN];int match[MAXN];int id[MAXN][MAXN];int n, m;char s[MAXN][MAXN];int path(int u){for(int v=1;v<=m;v++){if(G[u][v] && !vis[v]){vis[v] = 1;if(match[v] == -1 || path(match[v])){match[v] = u;return 1;}}}return 0;}int main(){int T, kcase = 1;scanf("%d", &T);while(T–){int N;scanf("%d", &N);memset(id, 0, sizeof(id));int x = 0;for(int i=1;i<=N;i++){scanf("%s", s[i] + 1);for(int j=1;j<=N;j++){if(s[i][j] == '#')id[i][j] = ++x;}}n = m = x;memset(G, 0, sizeof(G));FOR(i, 1, N){FOR(j, 1, N){if(s[i][j] == '#'){if(i > 1 && s[i-1][j] == '#')G[id[i-1][j]][id[i][j]] = 1;if(i < N && s[i+1][j] == '#')G[id[i+1][j]][id[i][j]] = 1;if(j > 1 && s[i][j-1] == '#')G[id[i][j-1]][id[i][j]] = 1;if(j < N && s[i][j+1] == '#')G[id[i][j+1]][id[i][j]] = 1;}}}int ans = 0;memset(match, -1, sizeof(match));for(int i=1;i<=n;i++){memset(vis, 0, sizeof(vis));ans += path(i);}printf("Case %d: %d\n", kcase++, ans / 2);}return 0;}
，劝君更尽一杯酒，西出阳关无故人。
