链接:https://ac.nowcoder.com/acm/problem/15107
来源:牛客网

随着海上运输石油泄漏的问题,一个新的有利可图的行业正在诞生,那就是撇***业。如今,在墨西哥湾漂浮的大量石油,吸引了许多商人的目光。这些商人们有一种特殊的飞机,可以一瓢略过整个海面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

题意:给出一个区域地图,油面是由"#“代表,海面是”.",商人可以一瓢略过整个海面20米乘10米这么大的长方形。(上下相邻或者左右相邻的格子,不能斜着来)当然,这要求一瓢撇过去的全部是油,如果一瓢里面有油有水的话,油就不能用,所以,要得到的油面必须是上下相邻或者左右相邻。

解题思路:dfs,很明显就是搜索。

#include <stdio.h>
int t, n, ans, cas = 0, odd, even;
char mp[52][52];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
void dfs(int x, int y) {
    if((x + y) % 2) //代表一半的区域
    odd ++;
    else 另一半
    even ++;
    mp[x][y] = '.';
    for(int i = 0; i < 4; i ++) {
        int s = x + dx[i];
        int e = y + dy[i];
        if(s >= 0 && s < n && e >= 0 && e < n && mp[s][e] == '#') {
            dfs(s, e);
        }
    }
}
int main() {
    scanf("%d", &t);
    while(t --) {
        ans = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; i ++) {
            scanf("%s", mp[i]);
        }
        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < n; j ++) {
                if(mp[i][j] == '#') {
                    odd = 0;
                    even = 0;
                    dfs(i, j);
                    ans += odd < even ? odd : even;
                }
            }
        }
        printf("Case %d: %d\n", ++cas, ans);
    }
    return 0;
}