石油采集（求联通区域） 2018多校寒假集训（dfs+二分匹配）-白红宇

石油采集（求联通区域） 2018多校寒假集训（dfs+二分匹配）

阅读量：4309 次

发布时间：2019-06-06

本文共 2354 字，大约阅读时间需要 7 分钟。

题目：

链接：

来源：牛客网

随着海上运输石油泄漏的问题，一个新的有利可图的行业正在诞生，那就是撇油行业。如今，在墨西哥湾漂浮的大量石油，吸引了许多商人的目光。这些商人们有一种特殊的飞机，可以一瓢略过整个海面20米乘10米这么大的长方形。（上下相邻或者左右相邻的格子，不能斜着来）当然，这要求一瓢撇过去的全部是油，如果一瓢里面有油有水的话，那就毫无意义了，资源完全无法利用。现在，商人想要知道，在这片区域中，他可以最多得到多少瓢油。

地图是一个N×N的网络，每个格子表示10m×10m的正方形区域，每个区域都被标示上了是油还是水

输入描述:

测试输入包含多条测试数据 测试数据的第一行给出了测试数据的数目T（T<75） 每个测试样例都用数字N（N<50）来表示地图区域的大小，接下来N行，每行都有N个字符，其中符号’.’表示海面、符号’#’表示油面。

输出描述:

输出格式如下“Case X: M”（X从1开始），M是商人可以最多得到的油量。

示例1

输入

16.......##..........#..#..#..##......

输出

Case 1: 3 题意：中文题不解释 思路：way1：dfs爆搜就OK啊，，，这么简单的题目不知道为什么当时没有出      way2：二分匹配

代码1：

#include
         
          #include
          
           #include
           
            #include
            
             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

代码2：（思路简单就不自己写了）

#include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              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
               
                >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

简单题

转载于:https://www.cnblogs.com/huangzzz/p/8446352.html

你可能感兴趣的文章