Description

地质学家有时会根据降雨流向将一片区域划分为不同的区域，这些区域被称为流域。

给定一张高程图（即一个二维的高度数组），请对地图进行标记，使得同属一个流域的区域具有相同的标记，并满足以下规则：

• 从每个格子出发，水最多只能流向其四个相邻格子中的一个。
• 对于每个格子，如果它的四个邻居中没有任何一个高度低于它自身，则水不会流动，该格子被称为汇。
• 否则，水会从该格子流向高度最低的邻居。
• 如果有多个邻居高度同为最低，则水会选择以下顺序中第一个最低的方向：北、 西、 东、 南。

所有直接或间接流向同一个汇的格子都属于同一个流域。每个流域应分配一个独特的小写字母作为标记，并且要保证：当将地图的所有行自上而下拼接成一个字符串时，所得字符串的字典序最小（特别地，最西北角的格子的流域标记总是 'a'）。

Input Format

输入的第一行包含地图的数量 $T$。接下来有 $T$ 个地图，每个地图的第一行为两个整数 $H$ 和 $W$，分别表示地图的高和宽（单位为格子数）。接下来的 $H$ 行，每行包含 $W$ 个整数，表示从北到南的每一行，从西到东的每一列，对应格子的高度。

Output Format

对于每组测试数据，输出 $1+H$ 行。第一行格式如下：

Case #$X$:

其中 $X$ 是测试编号，从 1 开始。接下来的 $H$ 行，输出每个格子的流域标记，顺序与输入一致。

4
3 3
9 6 3
5 9 6
3 5 9
1 10
0 1 2 3 4 5 6 7 8 7
2 3
7 6 7
7 6 7
5 5
1 2 3 4 5
2 9 3 9 6
3 3 0 8 7
4 9 8 9 8
5 6 7 8 9

Case #1:
a b b
a a b
a a a
Case #2:
a a a a a a a a a b
Case #3:
a a a
b b b
Case #4:
a a a a a
a a b b a
a b b b a
a b b b a
a a a a a

Hint

样例说明

在第 1 组数据中，右上角和左下角是汇。对角线上的水会流向左下角，因为那里高度较低（5 比 6 小）。

限制条件

• $T \leq 100$

小数据集（10 分）

• 时间限制：2 秒。
• $1 \leq H, W \leq 10$；
• $0 \leq \text{高度} < 10$；
• 最多有 2 个流域。

大数据集（23 分）

• 时间限制：3 秒。
• $1 \leq H, W \leq 100$；
• $0 \leq \text{高度} < 10,000$。
• 最多有 26 个流域。

翻译由 ChatGPT-4.1 完成。