石油采集

链接：https://www.nowcoder.net/acm/contest/76/A
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：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<cstdio> 
 3 #include<cstring> 
 4 #include<stdlib.h> 
 5 #include<limits.h> 
 6 #include<queue> 
 7 #include<cmath> 
 8 #include<algorithm> 
 9 using namespace  std;
10 #define maxn 2505 
11 char str[maxn][maxn];
12 int ans[maxn];
13 int map[maxn][maxn];
14 int a[maxn], b[maxn];
15 int n;
16 int v[maxn];
17 int dfs(int x)
18 {
19     for (int i = 1; i <= n * n; i++)
20     {
21         if (map[x][i] && !ans[i])
22         {
23             ans[i] = 1;
24             if (!v[i] || dfs(v[i]))
25             {
26                 v[i] = x;
27                 return 1;
28             }
29         }
30     }
31     return 0;
32 }
33 int  main()
34 {
35     int i, j, T, cases = 0;
36     scanf_s("%d", &T);
37     while (T--)
38     {
39         int x;
40         scanf_s("%d", &n);
41         memset(v, 0, sizeof(v));
42         memset(map, 0, sizeof(map));
43         memset(str, '', sizeof(str));
44         for (i = 1; i <= n; i++)
45             for (j = 1; j <= n; j++)
46                 cin >> str[i][j];
47         for (i = 1; i <= n; i++)
48             for (j = 1; j <= n; j++)
49             {
50                 if (str[i][j] == '#' && str[i][j - 1] == '#')
51                     map[(i - 1)*n + j][(i - 1)*n + j - 1] = 1;
52                 if (str[i][j] == '#' && str[i][j + 1] == '#')
53                     map[(i - 1)*n + j][(i - 1)*n + j + 1] = 1;
54                 if (str[i][j] == '#' && str[i - 1][j] == '#')
55                     map[(i - 1)*n + j][(i - 2)*n + j] = 1;
56                 if (str[i][j] == '#' && str[i + 1][j] == '#')
57                     map[(i - 1)*n + j][(i)*n + j] = 1;
58             }
59         /*for (i = 1; i <= n * n; i++)
60         {
61             for (j = 1; j <= n * n; j++)
62             {
63                 cout << map[i][j];
64             }
65             cout << endl;
66         }*/
67         int sum = 0;
68         for (i = 1; i <= n * n; i++)
69         {
70             memset(ans, 0, sizeof(ans));
71             if (dfs(i)) sum++;
72         }
73         printf("Case %d: %d
", ++cases, sum / 2);
74     }
75     return 0;
76 }
View Code

居然可以用二分匹配

 1 #include <iostream>
 2 #include <queue>
 3 #include <algorithm>
 4 #include <string.h>
 5 #include <math.h>
 6 #include <map>
 7 using namespace std;
 8 const int maxn=2000;
 9 int girl[maxn],used[maxn],line[maxn][maxn],path[60][60],temp1,temp2;
10 char a[60][60];
11 bool find(int x)
12 {
13     for (int i=1;i<temp2;i++)
14     if (line[x][i]&&!used[i]) //x与i有关系
15     {
16         used[i]=1;
17         if (girl[i]==0||find(girl[i])) //名花无主或者还能腾位置；
18         {
19             girl[i]=x;
20             return true;
21         }
22     }
23     return false;
24 }
25 int main()
26 {
27      
28     int t,n,ans,tt;
29     cin>>t;
30     tt=1;
31     while (t--)
32     {
33         ans=0;
34         temp1=temp2=1;
35         memset(line,0,sizeof(line));
36         memset(girl,0,sizeof(girl));
37         memset(path,0,sizeof(path));
38         cin>>n;
39         for (int i=1;i<=n;i++)
40             for (int j=1;j<=n;j++)
41             {
42                 cin>>a[i][j];
43                 if ((i+j)%2==0)
44                 path[i][j]=temp1++;
45                 else
46                 path[i][j]=temp2++;
47             }
48         for (int i=1;i<=n;i++)
49             for (int j=1;j<=n;j++)
50             {
51                 if ((i+j)%2==1&&a[i][j]=='#')
52                 {
53                     if (path[i-1][j]>=1&&a[i-1][j]=='#')
54                     line[path[i-1][j]][path[i][j]]=1;
55                     if (path[i+1][j]>=1&&a[i+1][j]=='#')
56                     line[path[i+1][j]][path[i][j]]=1;
57                     if (path[i][j-1]>=1&&a[i][j-1]=='#')
58                     line[path[i][j-1]][path[i][j]]=1;
59                     if (path[i][j+1]>=1&&a[i][j+1]=='#')
60                     line[path[i][j+1]][path[i][j]]=1;
61                 }
62             }
63         for (int i=1;i<temp1;i++)
64         {
65             memset(used,0,sizeof(used));
66             if (find(i))
67             ans++;
68         }
69         cout<<"Case "<<tt++<<": "<<ans<<endl;
70     }
71 }
View Code

dfs也可以做

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int n;
 6 char s[55][55];
 7 int num1,num2;
 8 void dfs(int x,int y)
 9 {
10     if(x>=1&&x<=n&&y>=1&&y<=n&&s[x][y]=='#')
11     {
12         if((x+y)%2)  num1++;
13         else   num2++;
14         s[x][y]='.';
15         dfs(x,y-1);
16         dfs(x,y+1);
17         dfs(x-1,y);
18         dfs(x+1,y);
19     }
20 }
21 int main()
22 {
23     int T;
24     scanf("%d",&T);
25     int CASE=1;
26     while(T--)
27     {
28         scanf("%d",&n);
29         int i,j;
30         for(i=1; i<=n; i++)
31         {
32             getchar();
33             for(j=1; j<=n; j++)
34                 scanf("%c",&s[i][j]);
35         }
36         int ans=0;
37         for(i=1; i<=n; i++)
38         {
39             for(j=1; j<=n; j++)
40             {
41                 if(s[i][j]=='#')
42                 {
43                     num1=0,num2=0;
44                     dfs(i,j);
45                     ans+=min(num1,num2);
46                 }
47             }
48         }
49         printf("Case %d: %d
",CASE++,ans);
50     }
51 }
View Code
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <map>
 5 #include <set>
 6 #include <bitset>
 7 #include <cctype>
 8 #include <cstdlib>
 9 #include <queue>
10 #include <cmath>
11 #include <stack>
12 #include <ctime>
13 #include <string>
14 #include <vector>
15 #include <sstream>
16 #include <functional>
17 #include <algorithm>
18 using namespace std;
19  
20 #define mem(a,n) memset(a,n,sizeof(a))
21 #define memc(a,b) memcpy(a,b,sizeof(b))
22 #define rep(i,a,n) for(int i=a;i<n;i++) ///[a,n)
23 #define dec(i,n,a) for(int i=n;i>=a;i--)///[n,a]
24 #define pb push_back
25 #define fi first
26 #define se second
27 #define IO ios::sync_with_stdio(false)
28 #define fre freopen("in.txt","r",stdin)
29 #define lson l,m,rt<<1
30 #define rson m+1,r,rt<<1|1
31 typedef long long ll;
32 typedef unsigned long long ull;
33 const double PI=acos(-1.0);
34 const double E=2.718281828459045;
35 const double eps=1e-8;
36 const int INF=0x3f3f3f3f;
37 const int MOD=258280327;
38 const int N=50+5;
39 const ll maxn=1e6+5;
40 const int dir[4][2]= {-1,0,1,0,0,-1,0,1};
41 int n,ans;
42 char a[N][N];
43 bool vis[N][N];
44 bool in(int x,int y)
45 {
46     if(x>=0&&x<n&&y>=0&&y<n) return true;
47     return false;
48 }
49 bool dfs(int x,int y)
50 {
51     rep(i,0,4)
52     {
53         int nx=x+dir[i][0],ny=y+dir[i][1];
54         if(in(nx,ny) && a[nx][ny]=='#')
55         {
56             a[x][y]='.';
57             if(!dfs(nx,ny))
58             {
59                 a[nx][ny]='#';
60                 ans++;
61                 return true;
62             }
63             a[x][y]='#';
64         }
65     }
66     return false;
67 }
68 int main()
69 {
70     int T;
71     scanf("%d",&T);
72     rep(cas,0,T)
73     {
74         scanf("%d",&n);
75         ans=0;
76         mem(vis,0);
77         rep(i,0,n) scanf("%s",a[i]);
78         rep(i,0,n)
79         {
80             rep(j,0,n)
81             {
82                 if(a[i][j]=='#')
83                     dfs(i,j);
84             }
85         }
86         printf("Case %d: %d
",cas+1,ans);
87     }
88     return 0;
89 }
View Code
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <set>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <stack>
#include <ctime>
#include <string>
#include <vector>
#include <sstream>
#include <functional>
#include <algorithm>
using namespace std;
 
#define mem(a,n) memset(a,n,sizeof(a))
#define memc(a,b) memcpy(a,b,sizeof(b))
#define rep(i,a,n) for(int i=a;i<n;i++) ///[a,n)
#define dec(i,n,a) for(int i=n;i>=a;i--)///[n,a]
#define pb push_back
#define fi first
#define se second
#define IO ios::sync_with_stdio(false)
#define fre freopen("in.txt","r",stdin)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
typedef unsigned long long ull;
const double PI=acos(-1.0);
const double E=2.718281828459045;
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const int MOD=258280327;
const int N=50+5;
const ll maxn=1e6+5;
const int dir[4][2]= {-1,0,1,0,0,-1,0,1};
int n,ans;
char a[N][N];
bool vis[N][N];
bool in(int x,int y)
{
    if(x>=0&&x<n&&y>=0&&y<n) return true;
    return false;
}
bool dfs(int x,int y)
{
    rep(i,0,4)
    {
        int nx=x+dir[i][0],ny=y+dir[i][1];
        if(in(nx,ny) && a[nx][ny]=='#')
        {
            a[x][y]='.';
            if(!dfs(nx,ny))
            {
                a[nx][ny]='#';
                ans++;
                return true;
            }
            a[x][y]='#';
        }
    }
    return false;
}
int main()
{
    int T;
    scanf("%d",&T);
    rep(cas,0,T)
    {
        scanf("%d",&n);
        ans=0;
        mem(vis,0);
        rep(i,0,n) scanf("%s",a[i]);
        rep(i,0,n)
        {
            rep(j,0,n)
            {
                if(a[i][j]=='#')
                    dfs(i,j);
            }
        }
        printf("Case %d: %d ",cas+1,ans);
    }
    return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/caiyishuai/p/8443194.html