Google Code Jam 2009资格赛 题目B Watersheds - xbl1986的专栏 - 博客频道 - CSDN.NET

Google Code Jam 2009资格赛 题目B Watersheds - xbl1986的专栏 - 博客频道 - CSDN.NET

分水岭

Problem 问题

Geologists sometimes divide an area of land into different regions based on where rainfall flows down to. These regions are called drainage basins.

地址学家有时候根据降雨量把一个陆地地区分成不同的区域。这些区域被称为流域。

Given an elevation map (a 2-dimensional array of altitudes), label the map such that locations in the same drainage basin have the same label, subject to the following rules.

给出了一个海拔地图（一个海拔的二维数组），标记这个地图，使得相同流域的位置具有相同的标签，服从于下面的规则。

• From each cell, water flows down to at most one of its 4 neighboring cells.
• 对于每一个单元，水流至少流向四个邻居之一的地方。
• For each cell, if none of its 4 neighboring cells has a lower altitude than the current cell's, then the water does not flow, and the current cell is called a sink.
• 对于每一个单元，如果它周围的四个邻居海拔都比它高，那么水就不流动了，并且当前的单元被称为水池。
• Otherwise, water flows from the current cell to the neighbor with the lowest altitude.
• 否则，水流从当前的单元流向海拔更低的单元。
• In case of a tie, water will choose the first direction with the lowest altitude from this list: North, West, East, South.
• 至于关系，水将会从北西东南中选择最低的海拔作为第一个流动的方向。（我加的理解，比如9旁边有2和3，则水流流向2而不是3）

Every cell that drains directly or indirectly to the same sink is part of the same drainage basin. Each basin is labeled by a unique lower-case letter, in such a way that, when the rows of the map are concatenated from top to bottom, the resulting string is lexicographically smallest. (In particular, the basin of the most North-Western cell is always labeled 'a'.)

每一个单元，直接或者间接的成到同样的水池，是相同流域的一部分。每一个流域被一个特殊的小写字母标记，这一点，地图上的行从上到下，得到的字符串字典最小的连接在一起。（特殊的，大多数西北单元的水池总是被标记为a）。（我加的理解，这个长句子……感觉还是谷歌翻译翻译的有点味道。我理解的就是从海拔高的地方流到水池，取路径最短的，如果一个流经了4个单元，一个流经了9个单元，则取4个单元的那个路径。）

Input 输入

The first line of the input file will contain the number of maps, T. T maps will follow, each starting with two integers on a line -- H and W -- the height and width of the map, in cells. The next H lines will each contain a row of the map, from north to south, each containing W integers, from west to east, specifying the altitudes of the cells.

输入文件的第一行将包含地图的数量，T。T个地图将紧随其后，每一个以一行有两个整数开始--H和W--地图的高度和宽度。接下来的H行，每一行都包含了地图的一行，从北到南，每行包含了W个整数，从西到东，指定了单元的海拔。

Output 输出

For each test case, output 1+H lines. The first line must be of the form

每一个测试案例，输出 1+H行。第一行必需从Case #X:开始

Case #X:

where X is the test case number, starting from 1. The next H lines must list the basin labels for each of the cells, in the same order as they appear in the input.

X是测试案例号，从1开始。接下来的H行必须列出每个单元的流域标签，以其在输入文件中出现的顺序。

Limits 限制

T ≤ 100; T，地图的个数小于100.

Small dataset 小数据

1 ≤ H, W ≤ 10; 高度和宽度大于等于一小于等于十。
0 ≤ altitudes < 10. 海拔大于等于零，小于十。
There will be at most two basins. 最多两个流域。

Large dataset 大数据

1 ≤ H, W ≤ 100; 高度和宽度大于等于一，小于等于一百。
0 ≤ altitudes < 10,000.海拔大于等于零，小于一万。
There will be at most 26 basins.最多26个流域。

Sample 例子

Input 输入

5
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
2 13
8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8

Output 输出

Case #1:
a b b        9是分水岭，从9沿着左上-右下的对角线水流动，西北优先标记a，然后是b，两个流域。
a a b
a a a
Case #2:
a a a a a a a a a b  8是分水岭，流向左右。两个流域。
Case #3:
a a a 这个难明白些。 767  7只能->6，而6没法流动成为水池，6<-7，而第一行的都无法流向第二行。
b b b              767  第二行相同，无法流向第一行，因此上下分ab。有点不好理解。
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
Case #5:
a b c d e f g h i j k l m  都是一样的，每个单元都是一个水池，只好编号了，字母表走了一遍。
n o p q r s t u v w x y z

Notes 注意

In Case #1, the upper-right and lower-left corners are sinks. Water from the diagonal flows towards the lower-left because of the lower altitude (5 versus 6).

在第一个地图中，右上角和左下角是流域。水从对角线流向更低的左边，因为海拔低（5对6）.

/*-----------------------------------------------------------------------------*/

从A的经验来看，弄明白怎么回事是很重要的……，灰常，灰常重要！

我又看了一边例子，把给出的例子解释了一遍，然后修正了一些翻译的内容。

例子是基本看明白了，思路是一点没有啊……。好吧，慢慢思考。

Read full article from Google Code Jam 2009资格赛 题目B Watersheds - xbl1986的专栏 - 博客频道 - CSDN.NET