CodeForces - 723D - D. Lakes in Berland

蔚落 2022-06-12 12:59 159阅读 0赞

--------------------

题目连接：[http://codeforces.com/problemset/problem/723/D][http_codeforces.com_problemset_problem_723_D]

## 题目描述 ##

### Description ###

The map of Berland is a rectangle of the size n × m, which consists of cells of size 1 × 1. Each cell is either land or water. The map is surrounded by the ocean.

Lakes are the maximal regions of water cells, connected by sides, which are not connected with the ocean. Formally, lake is a set of water cells, such that it’s possible to get from any cell of the set to any other without leaving the set and moving only to cells adjacent by the side, none of them is located on the border of the rectangle, and it’s impossible to add one more water cell to the set such that it will be connected with any other cell.

You task is to fill up with the earth the minimum number of water cells so that there will be exactly k lakes in Berland. Note that the initial number of lakes on the map is not less than k.

遥远的西方有一座小岛，小岛的四周环绕海洋，小岛可用一个n\*m的矩阵描述，每一个小区块要么是水域，要么是陆地。

我们定义湖泊为一个封闭的水域联通区间，换句话说：如果一片水域互相联通，且被陆地包围并不和海洋连通，那么这整片水域就是一个湖泊。

由于小岛人口密度急剧上升，岛主决定填湖造陆，使得湖泊数量变为k，保证原来的湖泊数量是不小于k的。

现在，请你帮忙岛主求出，最少需要填多少块水域才能满足岛主的需要。

### Input ###

The first line of the input contains three integers n, m and k (1 ≤ n, m ≤ 50, 0 ≤ k ≤ 50) — the sizes of the map and the number of lakes which should be left on the map.

The next n lines contain m characters each — the description of the map. Each of the characters is either ‘.’ (it means that the corresponding cell is water) or ‘\*’ (it means that the corresponding cell is land).

It is guaranteed that the map contain at least k lakes.

第一行三个整数 n, m , k (1 ≤ n, m ≤ 50, 0 ≤ k ≤ 50)

接下来n行每行1个字符串，长度为m，描述这个小岛，其中’\*’表示陆地，’.’表示水域

### Output ###

In the first line print the minimum number of cells which should be transformed from water to land.

In the next n lines print m symbols — the map after the changes. The format must strictly follow the format of the map in the input data (there is no need to print the size of the map). If there are several answers, print any of them.

It is guaranteed that the answer exists on the given data.

第一行一个整数，表示最少需要填的水域数量。

接下来n行每行1个字符串，长度为m，描述填完以后的小岛地图。

如果有多组解，输出任意一组。

### Sample Input ###

*  5 4 1
 *  *\*\**
 *  *..*
 *  *\*\**
 *  *\*.*
 *  ..\*\*

### Sample Output ###

*  1
 *  *\*\**
 *  *..*
 *  *\*\**
 *  *\*\**
 *  ..\*\*

## 解题思路 ##

用一个结构体记录一个点（x，y）dfs开始的地方，也就是一个湖的开始，s记录湖的面积，（每次bfs时加1）  
用一个全局变量 num，记录湖的个数（当湖为正确的湖的时候）  
那么问题来了，那种不算湖的怎么办，在bfs里面判断出界的时候把初始为1 的flag边为0，意思是，如果一个湖它能出界，那么一定到了地图的边缘，在地图边缘的湖是一定不算湖的，所以如果能bfs到出界，一定要经过边缘，所以标记这个湖，不计入总湖数，而且要把面积记为0。  
做完这些后，我们根据结构体中的s（面积）排序，用 **湖的数量 - k**， 得到的是需要填的湖的数量，从小开始填，然后记录每次填的面积，填湖的时候bfs填，因为已经记录了开始的点，所以这个bfs比较简单，只需要判断是否为点（水）就行，每次开始bfs的时候把这个点的map更改为\*。

## AC代码 ##

#include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    int n, m, k, num, flag, area = 0;
    char map[60][60];
    int vis[60][60];
    int to[4][2] = {0,1,0,-1,1,0,-1,0};
    struct node {
        int x, y, s;
    }cnt[6000];
    int cmp(node a, node b){
        return a.s < b.s;
    }
    void bfs(int x, int y) {
        vis[x][y] = 1;
        area++;
        for(int i = 0; i < 4; i++) {
            int tx = x + to[i][0];
            int ty = y + to[i][1];
            if(tx<0 || ty<0 || tx>n-1 || ty>m-1) {
                area = 0, flag = 0;
                continue;
            }
            if(map[tx][ty] == '*' || vis[tx][ty])
                continue;
            bfs(tx, ty);
        }
    }
    void bfs1(int x, int y) {
        map[x][y] = '*';
        for(int i = 0; i < 4; i++) {
            int tx = x + to[i][0];
            int ty = y + to[i][1];
            if(map[tx][ty] == '.') {
                bfs1(tx, ty);
            }
        }
    }
    int main () {
        scanf("%d %d %d", &n, &m, &k);
        num = 0;
        area = 0;
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n; i++) {
            scanf("%s", map[i]);
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                area = 0, flag = 1;
                if(map[i][j] == '.' && !vis[i][j]) {
                    bfs(i, j);
                    if(flag) {
                        cnt[num].x = i;
                        cnt[num].y = j;
                        cnt[num++].s = area; 
                    }
                }
            }
        }   
        sort(cnt, cnt+num, cmp);     
        int index = num - k;
        int sum = 0;
        for(int i = 0; i < index; i++) {
            sum += cnt[i].s;
            bfs1(cnt[i].x, cnt[i].y);
        }
        printf("%d\n", sum);
        for(int i = 0; i < n; i++) {
            printf("%s\n", map[i]);
        }
        return 0;
    }

[http_codeforces.com_problemset_problem_723_D]: http://codeforces.com/problemset/problem/723/D