海岸线

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 137 Accepted Submission(s): 76

Problem Description

欢迎来到珠海！

由于土地资源越来越紧张，使得许多海滨城市都只能依靠填海来扩展市区以求发展。作为Z市的决策人，在仔细观察了Z市地图之后，你准备通过填充某些海域来扩展Z市的海岸线到最长，来吸引更多的游客前来旅游度假。为了简化问题，假设地图为一个N*M的格子，其中一些是陆地，一些是可以填充的浅海域，一些是不可填充的深海域。这里定义海岸线的长度为一个联通块陆地（可能包含浅海域填充变为的陆地）的边缘长度，两个格子至少有一个公共边，则视为联通。

值得注意的是，这里Z市的陆地区域可以是不联通的，并且整个地图都处在海洋之中，也就是说，Z市是由一些孤岛组成的，比如像，夏威夷？

你的任务是，填充某些浅海域，使得所有岛屿的海岸线之和最长。

Input

输入第一行为T，表示有T组测试数据。
每组数据以两个整数N和M开始，表示地图的规模。接下来的N行，每一行包含一个长度为M的字符串，表示地图，‘.’表示陆地，’E’表示浅海域，’D’表示深海域。

[Technical Specification]

1. 1 <= T <= 100
2. 1 <= N, M <= 47

Output

对每组数据，先输出为第几组数据，然后输出最长的海岸线长度。

Sample Input

32 2EEEE3 3EEE.E.EEE3 3EEEDEDEEE

Sample Output

Case 1: 8Case 2: 16Case 3: 20

Hint

对于第三组样例，一种可行方案是：.E.D.D.E.这样5个孤立小岛的海岸线总长为4 * 5 = 20。

Author

Isea@WHU

Source

BestCoder Round #1

.... 什么也不说了http://www.kuangbin.net/archives/hdu4859这位代码很好, 这位题解很好http://blog.csdn.net/scf0920/article/details/38064593

搭配着看效果很好T T

#include <iostream>#include <cstring>using namespace std;#define rep(i, n) for (int i = 0, _n = (int)(n); i < _n; i++)#define fer(i, x, n) for (int i = (int)(x), _n = (int)(n); i < _n; i++)#define rof(i, n, x) for (int i = (int)(n), _x = (int)(x); i-- > _x; )#define fch(i, x) for (__typeof(x.begin()) i = x.begin(); i != x.end(); i++)#define sz(x) (int((x).size()))#define pb push_back#define mkp make_pair#define all(X) (X).begin(),(X).end()#define X first#define Y secondtemplate<class T> inline void smin(T &a, T b){if(b<a)a=b;}template<class T> inline void smax(T &a, T b){if(a<b)a=b;}template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}template<class T> inline void CLR(T &A){A.clear();}/** Constant List .. **/ //{const int dx4[] = {-1, 0, 1, 0};const int dy4[] = {0, 1, 0, -1};const int dx8[] = {-1, 0, 1, 0 , -1 , -1 , 1 , 1};const int dy8[] = {0, 1, 0, -1 , -1 , 1 , -1 , 1};const int mod = 1000000007;const int INF = 0x3f3f3f3f;//}template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}template<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}template<class T> inline T max(T a, T b, T c, T d){return max(max(a, b), max(c, d));}template<class T> inline T sqr(T a){return a*a;}template<class T> inline T cub(T a){return a*a*a;}////////////////////////////////////////////////////////////////////////////////const int MAXN = 10010;const int MAXM = 100010;struct Edge{    int to,next,cap,flow;}edge[MAXM];int tol;int head[MAXN];int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];void init(){    tol = 0;    memset(head,-1,sizeof(head));}void addedge(int u,int v,int w,int rw = 0){    edge[tol].to = v;edge[tol].cap = w;edge[tol].next = head[u];    edge[tol].flow = 0; head[u] = tol++;    edge[tol].to = u;edge[tol].cap = rw;edge[tol].next = head[v];    edge[tol].flow = 0;head[v] = tol++;}int sap(int start,int end,int N){    memset(gap,0,sizeof(gap));    memset(dep,0,sizeof(dep));    memcpy(cur,head,sizeof(head));    int u = start;    pre[u] = -1;    gap[0] = N;    int ans = 0;    while(dep[start] < N)    {        if(u == end)        {            int Min = INF;            for(int i = pre[u];i != -1;i = pre[edge[i^1].to])                if(Min > edge[i].cap - edge[i].flow)                    Min = edge[i].cap - edge[i].flow;            for(int i = pre[u];i != -1;i = pre[edge[i^1].to])            {                edge[i].flow += Min;                edge[i^1].flow -= Min;            }            u = start;            ans += Min;            continue;        }        bool flag = false;        int v;        for(int i = cur[u];i != -1;i = edge[i].next)        {            v = edge[i].to;            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u])            {                flag = true;                cur[u] = pre[v] = i;                break;            }        }        if(flag)        {            u = v;            continue;        }        int Min = N;        for(int i = head[u];i != -1;i = edge[i].next)            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)            {                Min = dep[edge[i].to];                cur[u] = i;            }        gap[dep[u]]--;        if(!gap[dep[u]])return ans;        dep[u] = Min+1;        gap[dep[u]]++;        if(u != start)u = edge[pre[u]^1].to;    }    return ans;}int T,n,m;char s[50][50];int id[50][50];int start,end;int main(){    //freopen("in.txt","r",stdin);    ios_base::sync_with_stdio(0);    scanf("%d",&T);    fer(tt,1,T+1){        scanf("%d%d",&n,&m);        fer(i,1,n+1) scanf("\n%s",s[i]+1);        rep(i,n+2) s[i][0]=s[i][m+1]=‘D‘;        rep(i,m+2) s[0][i]=s[n+1][i]=‘D‘;        init();        int cnt=0;        rep(i,n+2) rep(j,m+2) id[i][j]=++cnt;        start=0,end=cnt+1;        int sume = 0;        rep(i,n+2) rep(j,m+2){            rep(k,4){                int tx=i+dx4[k],ty=j+dy4[k];                if(tx<0 || tx>=n+2 || ty<0 || ty>=m+2) continue;                sume++; addedge(id[i][j],id[tx][ty],1);            }            if(s[i][j]!=‘E‘){                if( ((i+j)%2==1 && s[i][j]==‘.‘) || ((i+j)%2==0 && s[i][j]==‘D‘) ) addedge(start,id[i][j],INF);                else addedge(id[i][j],end,INF);            }        }        printf("Case %d: %d\n",tt,sume/2-sap(start,end,cnt+2) );    }    return 0;}

BestCoder Round #1 HDU4859 (海岸线)

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > BestCoder Round #1 HDU4859 (海岸线)

BestCoder Round #1 HDU4859 (海岸线)

海岸线

看完仍有疑问？有类似问题直接问程序猿