P13429 [GCJ 2009 Qualification] Watersheds

地质学家有时会根据降雨流向将一片区域划分为不同的区域，这些区域被称为**流域**。 给定一张高程图（即一个二维的高度数组），请对地图进行标记，使得同属一个流域的区域具有相同的标记，并满足以下规则： - 从每个格子出发，水最多只能流向其四个相邻格子中的一个。 - 对于每个格子，如果它的四个邻居中没有任何一个高度低于它自身，则水不会流动，该格子被称为**汇**。 - 否则，水会从该格子流向高度最低的邻居。 - 如果有多个邻居高度同为最低，则水会选择以下顺序中第一个最低的方向：北、 西、 东、 南。 所有直接或间接流向同一个汇的格子都属于同一个流域。每个流域应分配一个独特的小写字母作为标记，并且要保证：当将地图的所有行自上而下拼接成一个字符串时，所得字符串的字典序最小（特别地，最西北角的格子的流域标记总是 'a'）。

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

对于每组测试数据，输出 $1+H$ 行。第一行格式如下： Case #$X$: 其中 $X$ 是测试编号，从 1 开始。接下来的 $H$ 行，输出每个格子的流域标记，顺序与输入一致。

**样例说明** 在第 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 完成。