首页 > 代码库 > CF #375 (Div. 2) D. bfs

CF #375 (Div. 2) D. bfs

1、CF #375 (Div. 2)  D. Lakes in Berland   

2、总结:麻烦的bfs,但其实很水。。

3、题意:n*m的陆地与水泽,水泽在边界表示连通海洋。最后要剩k个湖,总要填掉多少个湖,然后输出。

技术分享
#include<bits/stdc++.h>#define F(i,a,b) for (int i=a;i<b;i++)#define FF(i,a,b) for (int i=a;i<=b;i++)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define LL long longusing namespace std;const int N=2100,MAX=1000100;struct Node{    int i,j,num;    bool operator < (const Node &a)const{        return num>a.num;    }};int n,m,k,num,flag;int diri[4]={0,0,1,-1};int dirj[4]={1,-1,0,0};int vis[80][80];char mapn[80][80];bool charge(Node e){    if(mapn[e.i][e.j]==.&&e.i>=0&&e.i<n&&e.j>=0&&e.j<m&&!vis[e.i][e.j])        return true;    return false;}bool charge2(Node e){    if(e.i==0||e.i==n-1||e.j==0||e.j==m-1)        return true;    return false;}void bfs(int i,int j){    queue<Node>Q;    Node st,en;    st.i=i,st.j=j;    vis[i][j]=1;    Q.push(st);    if(charge2(st)){flag=0;}    while(!Q.empty())    {        st=Q.front();Q.pop();        F(l,0,4){            en.i=st.i+diri[l];            en.j=st.j+dirj[l];            if(charge(en)){                if(charge2(en))flag=0;                vis[en.i][en.j]=1;                Q.push(en);                num++;            }        }    }}void bfs2(int i,int j){    queue<Node>Q;    Node st,en;    st.i=i,st.j=j;    vis[i][j]=1;    Q.push(st);    while(!Q.empty())    {        st=Q.front();Q.pop();        F(l,0,4){            en.i=st.i+diri[l];            en.j=st.j+dirj[l];            if(mapn[en.i][en.j]==.){                mapn[en.i][en.j]=*;                Q.push(en);            }        }    }}int main(){    while(~scanf("%d%d%d",&n,&m,&k))    {        int num1=0;        priority_queue<Node>Q;        mes(vis,0);        F(i,0,n)scanf("%s",mapn[i]);        F(i,0,n) F(j,0,m){            if(mapn[i][j]==.&&i>=0&&i<n&&j>=0&&j<m&&!vis[i][j]){                num=1,flag=1;                bfs(i,j);                if(flag){                    num1++;                    Node ans;ans.i=i,ans.j=j,ans.num=num;                    Q.push(ans);                }            }        }        mes(vis,0);        int sum=0;        num1-=k;        while(num1--){            Node ans=Q.top();Q.pop();            sum+=ans.num;            mapn[ans.i][ans.j]=*;            bfs2(ans.i,ans.j);        }        cout<<sum<<endl;        F(i,0,n)printf("%s\n",mapn[i]);    }    return 0;}
View Code

 

CF #375 (Div. 2) D. bfs