题目：
链接：https://www.nowcoder.com/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
题意：中文题不解释
思路：way1：dfs爆搜就OK啊，，，这么简单的题目不知道为什么当时没有出
way2：二分匹配
代码1：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int n,m; char mp[106][106]; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int ans1,ans2; void DFS(int i,int j) { int nx,ny; if(i<0||i>=m||j<0||j>=n||mp[i][j]=='.') return ; if((i+j)%2==0)ans1++; else ans2++; mp[i][j]='.'; for(int zz=0;zz<4;zz++) { nx=i+dx[zz]; ny=j+dy[zz]; DFS(nx,ny); } return ; } int main() { int i,j,res=0; int t; cin>>t; for(int o=1;o<=t;o++){ cin>>m; n=m; getchar(); for(i=0;i<m;i++) { for(j=0;j<n;j++) { scanf("%c",&mp[i][j]); } getchar(); } for(i=0;i<m;i++) for(j=0;j<n;j++) { if(mp[i][j]=='#') { ans1=0; ans2=0; DFS(i,j); res+=min(ans1,ans2); } } printf("Case %d: %d ",o,res); } return 0; }
代码2：（思路简单就不自己写了）
#include <iostream> #include <queue> #include <algorithm> #include <string.h> #include <math.h> #include <map> using namespace std; const int maxn=2000; int girl[maxn],used[maxn],line[maxn][maxn],path[60][60],temp1,temp2; char a[60][60]; bool find(int x) { for (int i=1;i<temp2;i++) if (line[x][i]&&!used[i]) //x与i有关系 { used[i]=1; if (girl[i]==0||find(girl[i])) //名花无主或者还能腾位置； { girl[i]=x; return true; } } return false; } int main() { int t,n,ans,tt; cin>>t; tt=1; while (t--) { ans=0; temp1=temp2=1; memset(line,0,sizeof(line)); memset(girl,0,sizeof(girl)); memset(path,0,sizeof(path)); cin>>n; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { cin>>a[i][j]; if ((i+j)%2==0) path[i][j]=temp1++; else path[i][j]=temp2++; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { if ((i+j)%2==1&&a[i][j]=='#') { if (path[i-1][j]>=1&&a[i-1][j]=='#') line[path[i-1][j]][path[i][j]]=1; if (path[i+1][j]>=1&&a[i+1][j]=='#') line[path[i+1][j]][path[i][j]]=1; if (path[i][j-1]>=1&&a[i][j-1]=='#') line[path[i][j-1]][path[i][j]]=1; if (path[i][j+1]>=1&&a[i][j+1]=='#') line[path[i][j+1]][path[i][j]]=1; } } for (int i=1;i<temp1;i++) { memset(used,0,sizeof(used)); if (find(i)) ans++; } cout<<"Case "<<tt++<<": "<<ans<<endl; } }
简单题