2018年全国多校算法寒假训练营练习比赛（第四场） A 石油采集

链接：https://www.nowcoder.net/acm/contest/76/A
来源：牛客网

题目描述

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

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

输入描述:

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

输出描述:

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

示例1
输入

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

输出

Case 1: 3

分析：一开始想这个题目的时候，觉得并不是很好写，可能还是代码实现能力有待提高，感觉上纯搜的话，可能会有很多种情况要考虑，考虑该点的前后左右分别有多少个连续的#，然后再去计算，然后学习了别人的方法，总结一下，首先对于一个#的点来说，他的上下左右的坐标和都是与他奇偶性不同的，因此我们只要计算出有多少个连续的点和为奇数，多少个和为偶数，连续的一奇一偶就能组成一个答案，那么我们只要把能匹配上的算出来，就可以了，为了避免重复计算，踩过的点都把其变成点即可

#include<bits/stdc++.h>
#define cl(arr,val) memset(arr,val,sizeof(arr));
using namespace std;
char s[100][100];
int c0,c1;
int N;
void dfs(int x,int y)
{
    if(x<1||x>N||y<0||y>=N||s[x][y]=='.')return;
    ((x+y)&1)?c0++:c1++;
    s[x][y]='.';
    dfs(x+1,y);
    dfs(x-1,y);
    dfs(x,y+1);
    dfs(x,y-1);
    return;
}
int main()
{
    int T;
    cin>>T;
    for(int Case=1;Case<=T;Case++)
    {
        cin>>N;
        int ans=0;
        for(int i=1;i<=N;i++)
        {
            scanf("%s",s[i]);
        }
        for(int i=1;i<=N;i++)
        {
            for(int j=0;j<N;j++)
            {
                if(s[i][j]=='#')
                {
                    c0=c1=0;
                    dfs(i,j);
                    ans+=min(c0,c1);
                }
            }
        }
        printf("Case %d: %d\n",Case,ans);
    }
    return 0;
}