题目描述

随着海上运输石油泄漏的问题，一个新的有利可图的行业正在诞生，那就是撇***业。如今，在墨西哥湾漂浮的大量石油，吸引了许多商人的目光。这些商人们有一种特殊的飞机，可以一瓢略过整个海面20米乘10米这么大的长方形。（上下相邻或者左右相邻的格子，不能斜着来）当然，这要求一瓢撇过去的全部是油，如果一瓢里面有油有水的话，那就毫无意义了，资源完全无法利用。现在，商人想要知道，在这片区域中，他可以最多得到多少瓢油。

地图是一个N×N的网络，每个格子表示10m×10m的正方形区域，每个区域都被标示上了是油还是水

输入格式

测试输入包含多条测试数据 测试数据的第一行给出了测试数据的数目T（T<75） 每个测试样例都用数字N（N<50）来表示地图区域的大小，接下来N行，每行都有N个字符，其中符号’.’表示海面、符号’#’表示油面。。

输出格式

输出格式如下“Case X: M”（X从1开始），M是商人可以最多得到的油量。

输入输出样例 #1

输入 #1

1
6
......
.##...
......
.#..#.
.#..##
......

输出 #1

Case 1: 3

思路：

1.直接用dfs或者bfs来搜连通块难以得到每个连通块对答案的最大贡献，实现比较麻烦，观察题目不难得出，相邻（上下左右）的两个油田可以得到一瓢油。

2.通过观察分析，一个位置的横纵坐标之和x+y，与之相邻位置的便是x+y+1或x+y-1，可得任意相邻的两个油田的横纵坐标之和必然是一奇一偶配对出现，可以通过统计当前区块下奇数和偶数的个数，然后进行奇偶配对，最终的结果则是取奇偶中小的值，即min(odd,even)；

3.为什么这样可以得到的答案是正确的呢？首先连通区域中的奇偶情况无非三种情况，我们用1表示奇数，0表示偶数， 要么cnt(1)==cnt(0),要么一大一小，对于第一种情况，因为区域内1和0是相邻的，并且相邻之间不可能奇偶性相同，那么在最优的情况下，每个1和0都可以凑成一对，可以用反证法，若0配对完了还剩下1，那说明1多了，这与cnt0==cnt1违背，可能有人会说如果多出一个0和一个1不相邻呢。这种情况是可能出现的，但是题目要求是最大值，所以我们只考虑最优情况。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 55;
char g[N][N];
int T,n,odd,even;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

void dfs(int x ,int y)
{
    if((x+y)&1) odd++;
    else even++;
    g[x][y]='.';
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<0 || nx>=n || ny<0 || ny>=n || g[nx][ny]=='.') continue;
        dfs(nx,ny);
    }
}

int main()
{
    cin>>T;
    for(int i=1 ;i<=T ;i++)
    {
        cin>>n;
        for(int i=0;i<n;i++) scanf("%s",g[i]);
        int res=0;
        for(int i=0;i<n;i++)
         for(int j=0;j<n;j++)
         {
             if(g[i][j]=='#')
             {
                 odd=0,even=0;
                 dfs(i,j);
                 res+=min(odd , even);
             }
         }
         cout<<"Case "<<T<<": "<<res<<endl;
    }
    return 0;
}