牛客网 2018年全国多校算法寒假训练营练习比赛（第四场） A.石油采集-DFS
菜哭了。。。
A.石油采集
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
随着海上运输石油泄漏的问题，一个新的有利可图的行业正在诞生，那就是撇油行业。如今，在墨西哥湾漂浮的大量石油，吸引了许多商人的目光。这些商人们有一种特殊的飞机，可以一瓢略过整个海面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
这个题只能说我自己有病，一开始感觉可以搜索，也可以二分图匈牙利匹配，也可以暴力，后来暴力写太挫了，超内存了？？？
赛后补题，搜索写就可以写过，也有人暴力过的，也有人匈牙利过的，乱七八糟的。
代码:
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 char s[100][100]; 8 int ans1,ans2,n; 9 void dfs(int x,int y){ 10 if(x<0||x>=n||y<0||y>=n||s[x][y]=='.') 11 return ; 12 if((x+y)%2==1)++ans1; 13 else ++ans2; 14 s[x][y]='.'; 15 dfs(x+1,y); 16 dfs(x-1,y); 17 dfs(x,y+1); 18 dfs(x,y-1); 19 } 20 int main(){ 21 int t; 22 scanf("%d",&t); 23 int h=0; 24 while(t--){ 25 scanf("%d",&n); 26 int ans=0; 27 for(int i=0;i<n;i++)scanf("%s",s[i]); 28 for(int i=0;i<n;i++) 29 for(int j=0;j<n;j++) 30 if(s[i][j]=='#'){ 31 ans1=0;ans2=0; 32 dfs(i,j); 33 ans+=min(ans1,ans2); 34 } 35 printf("Case %d: %d ",++h,ans); 36 } 37 }