codeforces 723D（DFS）

题目链接：http://codeforces.com/problemset/problem/723/D

题意：n*m的矩阵中，'*'代表陆地，'.'代表水，连在一起且不沿海的水形成湖泊。问最少填多少块water能使湖泊数量降到k个。

思路：本来最有把握的一次CF，D题小错误一直RE，C题最后也FST了......

先DFS出各湖泊的大小并用其中一个点存在结构体中，最后有num0个湖泊，再按湖泊的大小排序，需要填的湖泊为前n-k小的湖泊，简单DFS一下就好了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

char a[55][55];

bool vis[55][55];

int turnx[10] = {-1,1,0,0};

int turny[10] = {0,0,-1,1};

int n,m,k,num,flag;

struct node

{

    int num;

    int x;

    int y;

}q[3000];

bool cmp(node a,node b)

{

    return a.num < b.num;

}

bool in(int x,int y)

{

    if(x < 1 || y < 1 || x > n || y > m)

        return 0;

    return 1;

}

void dfs(int x,int y)

{

    if(vis[x][y] || a[x][y] == '*')

        return;

    num++;

    vis[x][y] = 1;

    for(int i = 0; i < 4; i++)

    {

        int nx = x + turnx[i];

        int ny = y + turny[i];

        if(!in(nx,ny))

        {

            num = 0;

            flag = 0;

            continue;

        }

        if(a[nx][ny] == '*' || vis[nx][ny])

            continue;

        dfs(nx,ny);

    }

}

void dfs1(int x,int y)

{

    a[x][y] = '*';

    for(int i = 0; i < 4; i++)

    {

        int nx = x + turnx[i];

        int ny = y + turny[i];

        if(a[nx][ny] == '*' )

            continue;

        dfs1(nx,ny);

    }

}

int main()

{

    scanf("%d %d %d",&n,&m,&k);

    int num0 = 0,ans = 0;

    for(int i = 1; i <= n; i++)

        scanf("%s",a[i] + 1);

    for(int i = 1; i <= n; i++)

    {

        for(int j = 1; j <= m; j++)

        {

            num = 0,flag = 1;

            if(!vis[i][j] && a[i][j] == '.')

            {

                dfs(i,j);

                if(flag)

                {

                    q[num0].num = num;

                    q[num0].x = i;

                    q[num0].y = j;

                    num0++;

                }

            }

        }

    }

    sort(q,q+num0,cmp);

    for(int i = 0; i < num0 - k; i++)

        ans += q[i].num;

    printf("%d\n",ans);

    for(int i = 0; i < num0 - k; i++)

        dfs1(q[i].x,q[i].y);

    for(int i = 1; i <= n; i++)

        printf("%s\n",a[i]+1);

    return 0;

}