分数: 400 点
问题陈述
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} is #,位于 i从顶部开始的第行和 j左起第 列包含一个草莓;如果 s_{i, j} is .,该部分不包含一个。 K 出现 #s。
高桥想把这个蛋糕切成 K 碎片并将其提供给参赛者。每一件作品都必须满足以下条件:
- 具有矩形形状。
- 恰好包含一个草莓。
一种可能的切蛋糕方法如下所示:

找到一种切蛋糕并满足条件的方法。我们可以证明,无论草莓的数量和位置如何,这总是可能的。
约束
- 1 \leq H \leq 300
- 1 \leq W \leq 300
- 1 \leq K \leq H \times W
- s_{i, j} is
#or.. - 正好有 K 出现
#in s.
输入
输入由标准输入按以下格式给出:
H W K
s_{1, 1} s_{1, 2} \cdots s_{1, W}
s_{2, 1} s_{2, 2} \cdots s_{2, W}
:
s_{H, 1} s_{H, 2} \cdots s_{H, W}
输出
分配号码 1, 2, 3, \dots, K 到 K 切割后获得的碎片,顺序任意。然后,让 a_{i, j} 是代表包含位于 i从顶部开始的第行和 j蛋糕左侧第 3 列。输出应采用以下格式:
a_{1, 1} \ a_{1, 2} \ \cdots \ a_{1, W}
a_{2, 1} \ a_{2, 2} \ \cdots \ a_{2, W}
:
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