시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 46 | 39 | 38 | 88.372% |
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.
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'.)
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.
Limits
For each test case, output 1+H lines. The first line must be of the form
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.
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
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 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
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).
Contest > Google > Code Jam > Google Code Jam 2009 > Qualification Round B1번