AT_ddcc2020_qual_c.Strawberry Cakes

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

chokudai 在 DDCC 2020 本赛中为参赛者准备了一个长方形的蛋糕。

这个蛋糕通过 $H-1$ 条横向切缝和 $W-1$ 条纵向切缝，被等分成了 $H \times W$ 个区域。在这些区域中，有 $K$ 个区域各放有一个草莓。

草莓的位置由 $H \times W$ 个字符 $s_{i,j}$ （ $1 \leq i \leq H, 1 \leq j \leq W$ ）给出。当 $s_{i,j}$ 为 # 时，表示从上往下第 $i$ 行、从左往右第 $j$ 列的区域有一个草莓；当 $s_{i,j}$ 为 . 时，表示该区域没有草莓。字符 # 恰好出现 $K$ 次。

现在，chokudai 想要沿着切缝将蛋糕切成 $K$ 块，并分发给参赛者。切分后，每一块都必须满足以下条件：

形状为长方形。
恰好包含 $1$ 个草莓。

例如，下图是一个可能的切分方式。

请你求出一种满足条件的蛋糕切分方式。无论草莓的数量和位置如何，总能找到一种切分方式。

输入格式

输入以如下格式从标准输入读入。

$H$ $W$ $K$
$s_{1,1} s_{1,2} \cdots s_{1,W}$
$s_{2,1} s_{2,2} \cdots s_{2,W}$
$\vdots$
$s_{H,1} s_{H,2} \cdots s_{H,W}$

输出格式

请为切分后的 $K$ 块蛋糕任意编号为 $1,2,3,\dots,K$ ，并输出一个 $H \times W$ 的矩阵。矩阵中第 $i$ 行第 $j$ 列的数字 $a_{i,j}$ 表示该区域属于哪一块蛋糕。

$a_{1,1} a_{1,2} \cdots a_{1,W}$
$a_{2,1} a_{2,2} \cdots a_{2,W}$
$\vdots$
$a_{H,1} a_{H,2} \cdots a_{H,W}$

如果存在多种切分方式，输出其中任意一种即可。

输入输出样例

输入#1
```
3 3 5
#.#
.#.
#.#
```
输出#1
```
1 2 2
1 3 4
5 5 4
```

输入#2

3 7 7
#...#.#
..#...#
.#..#..

输出#2

1 1 2 2 3 4 4
6 6 2 2 3 5 5
6 6 7 7 7 7 7

输入#3

13 21 106
.....................
.####.####.####.####.
..#.#..#.#.#....#....
..#.#..#.#.#....#....
..#.#..#.#.#....#....
.####.####.####.####.
.....................
.####.####.####.####.
....#.#..#....#.#..#.
.####.#..#.####.#..#.
.#....#..#.#....#..#.
.####.####.####.####.
.....................

输出#3

12 12 23 34 45 45 60 71 82 93 93 2 13 24 35 35 17 28 39 50 50
12 12 23 34 45 45 60 71 82 93 93 2 13 24 35 35 17 28 39 50 50
12 12 56 89 89 89 60 104 82 31 31 46 13 24 35 35 61 61 39 50 50
12 12 67 67 100 100 60 9 9 42 42 57 13 24 6 72 72 72 72 72 72
12 12 78 5 5 5 20 20 20 53 68 68 90 24 6 83 83 83 83 83 83
16 16 27 38 49 49 64 75 86 97 79 79 90 101 6 94 94 105 10 21 21
16 16 27 38 49 49 64 75 86 97 79 79 90 101 6 94 94 105 10 21 21
32 32 43 54 65 65 80 11 106 95 22 22 33 44 55 55 70 1 96 85 85
32 32 43 54 76 76 91 11 106 84 84 4 99 66 66 66 81 1 96 74 74
14 14 3 98 87 87 102 11 73 73 73 4 99 88 77 77 92 92 63 63 63
25 25 3 98 87 87 7 29 62 62 62 15 99 88 77 77 103 19 30 52 52
36 36 47 58 69 69 18 29 40 51 51 26 37 48 59 59 8 19 30 41 41
36 36 47 58 69 69 18 29 40 51 51 26 37 48 59 59 8 19 30 41 41

说明/提示

数据范围

$1 \leq H \leq 300$
$1 \leq W \leq 300$
$1 \leq K \leq H \times W$
$s_{i,j}$ 为 # 或 .
# 在 $s$ 中恰好出现 $K$ 次

样例解释 1

例如，下图展示了一种切分方式。

样例解释 2

例如，下图展示了一种切分方式。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页