链接：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; } }
运行结果
