D. Lakes in Berland

Codeforces

IDCF723D

Time2000ms

Memory256MB

Difficulty—

dfs and similardsugraphsgreedyimplementation

English · Original

Chinese · Translation

Formal · Original

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_. ## 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. ## 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. [samples] ## Note In the first example there are only two lakes — the first consists of the cells (2, 2) and (2, 3), the second consists of the cell (4, 3). It is profitable to cover the second lake because it is smaller. Pay attention that the area of water in the lower left corner is not a lake because this area share a border with the ocean.

[{"iden":"statement","content":"Berland 的地图是一个大小为 $n × m$ 的矩形，由 $1 × 1$ 的单元格组成。每个单元格要么是陆地，要么是水。地图被海洋包围。\n\n_湖泊_ 是由侧面相连的最大水单元格区域，且不与海洋相连。形式上，湖泊是一组水单元格，满足：从集合中的任意一个单元格出发，可以仅通过相邻（共享边）的单元格到达集合中的任意其他单元格，且集合中没有任何单元格位于矩形的边界上，并且无法再向集合中添加任何一个水单元格使其与集合中其他单元格相连。\n\n你的任务是将最少数量的水单元格填为陆地，使得 Berland 中恰好剩下 $k$ 个湖泊。注意，地图上初始的湖泊数量不少于 $k$。\n\n输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 ≤ n, m ≤ 50$，$0 ≤ k ≤ 50$）——地图的尺寸以及应保留的湖泊数量。\n\n接下来的 $n$ 行每行包含 $m$ 个字符，描述地图。每个字符要么是 '_._'（表示对应单元格是水），要么是 '_*_'（表示对应单元格是陆地）。\n\n保证地图中至少包含 $k$ 个湖泊。\n\n第一行输出需要从水变为陆地的最少单元格数量。\n\n接下来的 $n$ 行每行输出 $m$ 个字符——变化后的地图。格式必须严格遵循输入数据的格式（无需打印地图尺寸）。如果有多个答案，输出任意一个即可。\n\n保证在给定数据下答案存在。\n\n在第一个例子中，只有两个湖泊：第一个由单元格 $(2, 2)$ 和 $(2, 3)$ 组成，第二个由单元格 $(4, 3)$ 组成。填掉第二个湖泊更划算，因为它更小。请注意，左下角的水区域不是湖泊，因为它与海洋相邻。 \n\n"},{"iden":"input","content":"输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 ≤ n, m ≤ 50$，$0 ≤ k ≤ 50$）——地图的尺寸以及应保留的湖泊数量。接下来的 $n$ 行每行包含 $m$ 个字符，描述地图。每个字符要么是 '_._'（表示对应单元格是水），要么是 '_*_'（表示对应单元格是陆地）。保证地图中至少包含 $k$ 个湖泊。"},{"iden":"output","content":"第一行输出需要从水变为陆地的最少单元格数量。接下来的 $n$ 行每行输出 $m$ 个字符——变化后的地图。格式必须严格遵循输入数据的格式（无需打印地图尺寸）。如果有多个答案，输出任意一个即可。保证在给定数据下答案存在。"},{"iden":"examples","content":"输入\n5 4 1\n*****\n..***\n**.*.\n**..*\n**\n输出\n1\n*****\n..***\n******\n**..*\n**\n\n输入\n3 3 0\n***\n*.*\n***\n输出\n1\n***\n***\n***"},{"iden":"note","content":"在第一个例子中，只有两个湖泊：第一个由单元格 $(2, 2)$ 和 $(2, 3)$ 组成，第二个由单元格 $(4, 3)$ 组成。填掉第二个湖泊更划算，因为它更小。请注意，左下角的水区域不是湖泊，因为它与海洋相邻。 "}]}

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ be the dimensions of the grid. Let $ G = (V, E) $ be a grid graph with $ n \times m $ cells, where each cell is either water ($ \texttt{.} $) or land ($ \texttt{*} $). Let $ \mathcal{W} \subseteq V $ be the set of water cells. Let $ \mathcal{O} \subseteq \mathcal{W} $ be the set of water cells adjacent to the grid boundary (ocean-connected). Let $ \mathcal{L} $ be the set of lakes: maximal connected components of $ \mathcal{W} \setminus \mathcal{O} $ under 4-directional adjacency. **Constraints** 1. $ 1 \leq n, m \leq 50 $ 2. $ 0 \leq k \leq 50 $ 3. $ |\mathcal{L}| \geq k $ 4. Each lake is a connected component of water cells not touching the grid boundary. **Objective** Find the minimum number of water cells to convert to land such that exactly $ k $ lakes remain. Let $ \mathcal{L} = \{L_1, L_2, \dots, L_r\} $ with $ r \geq k $, and let $ s_i = |L_i| $ be the size of lake $ L_i $. Sort lakes by size: $ s_{(1)} \leq s_{(2)} \leq \dots \leq s_{(r)} $. Select the $ r - k $ smallest lakes to eliminate. Minimize total cells filled: $ \sum_{i=1}^{r-k} s_{(i)} $. Output the resulting grid after converting those cells to land.

Samples

Input #1

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

Output #1

1
****
*..*
****
****
..**

Input #2

3 3 0
***
*.*
***

Output #2

1
***
***
***

API Response (JSON)

{
  "problem": {
    "name": "D. Lakes in Berland",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF723D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\n\n_Lakes_ are the maximal regions ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"Berland 的地图是一个大小为 $n × m$ 的矩形，由 $1 × 1$ 的单元格组成。每个单元格要么是陆地，要么是水。地图被海洋包围。\\n\\n_湖泊_ 是由侧面相连的最大水单元格区域，且不与海洋相连。形式上，湖泊是一组水单元格，满足：从集合中的任意一个单元格出发，可以仅通过相邻（共享边）的单元格到达集合中的任意其他单元格，且集...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ be the dimensions of the grid.  \nLet $ G = (V, E) $ be a grid graph with $ n \\times m $ cells, where each cell is either water ($ \\texttt{.} $) or land ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments