牛客 石油采集题解
链接：https://ac.nowcoder.com/acm/contest/76/A?&headNav=www
来源：牛客网
题目描述
随着海上运输石油泄漏的问题，一个新的有利可图的行业正在诞生，那就是撇***业。如今，在墨西哥湾漂浮的大量石油，吸引了许多商人的目光。这些商人们有一种特殊的飞机，可以一瓢略过整个海面20米乘10米这么大的长方形。（上下相邻或者左右相邻的格子，不能斜着来）当然，这要求一瓢撇过去的全部是油，如果一瓢里面有油有水的话，那就毫无意义了，资源完全无法利用。现在，商人想要知道，在这片区域中，他可以最多得到多少瓢油。
地图是一个N×N的网络，每个格子表示10m×10m的正方形区域，每个区域都被标示上了是油还是水
输入描述:
测试输入包含多条测试数据
测试数据的第一行给出了测试数据的数目T（T<75）
每个测试样例都用数字N（N<50）来表示地图区域的大小，接下来N行，每行都有N个字符，其中符号’.’表示海面、符号’#’表示油面。
输出描述:
输出格式如下“Case X: M”（X从1开始），M是商人可以最多得到的油量。
输入
1
6
......
.##...
......
.#..#.
.#..##
......
输出
Case 1: 3
题目分析
这个题主要考察DFS+连通块的判断.对于两个连通块,其横纵坐标之和一奇一偶,在一次DFS中,连通块的个数就是奇数点和偶数点个数的最小值(因为一奇一偶构成一个连通块).所以每次深搜时得先统计odd和even的个数.
另外关于奇数偶数的判断可以使用位运算 & ,可以点击这里了解,当然也可以使用%运算.
AC代码
#include<iostream>
#include<string.h>
using namespace std;
int n, t,tx,ty, total,odd,even;
char map[55][55];
int book[55][55];
int NEXT[4][2] = {
{
-1,0},{
0,1},{
1,0},{
0,-1} };//四个方向
void dfs(int x, int y) {
//判断改点的奇偶性
if ((x + y) & 1) {
odd++;
}
else {
even++;
}
for (int i = 0; i < 4; i++) {
tx = x + NEXT[i][0];
ty = y + NEXT[i][1];
if (tx < 1 || tx > n || ty < 1 || ty > n) {
continue;
}
if (map[tx][ty] == '#' && !book[tx][ty]) {
book[tx][ty] = 1;
dfs(tx, ty);
}
}
}
int main() {
cin >> t;
for (int i = 1; i <= t; i++) {
memset(book, 0, sizeof(book));
total = 0;
cin >> n;
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
cin >> map[j][k];
}
}
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
if (map[j][k] == '#' && !book[j][k]) {
odd = 0;
even = 0;
book[j][k] = 1;
dfs(j, k);
total += min(odd, even);
}
}
}
cout << "Case " << i << ": " << total << endl;
}
}
