p*****u
发帖数: 310 | 1 A group of farmers has some elevation data, and we’re going to help them
understand how rainfall flows over their farmland. We’ll represent the land
as a two-dimensional array of altitudes and use the following model, based
on the idea that water flows downhill:
If a cell’s four neighboring cells all have higher altitudes, we call this
cell a sink; water collects in sinks. Otherwise, water will flow to the
neighboring cell with the lowest altitude. If a cell is not a sink, you may
assume it has a unique lowest neighbor and that this neighbor will be lower
than the cell.
请给个答案吧
Cells that drain into the same sink – directly or indirectly – are said to
be part of the same basin.
Your challenge is to partition the map into basins. In particular, given a
map of elevations, your code should partition the map into basins and output
the sizes of the basins, in descending order.
Assume the elevation maps are square. Input will begin with a line with one
integer, S, the height (and width) of the map. The next S lines will each
contain a row of the map, each with S integers – the elevations of the S
cells in the row. Some farmers have small land plots such as the examples
below, while some have larger plots. However, in no case will a farmer have
a plot of land larger than S = 5000.
Your code should output a space-separated list of the basin sizes, in
descending order. (Trailing spaces are ignored.)
A few examples are below.
Input:
3
1 5 2
2 4 7
3 6 9
Output: 7 2 | c*******e
发帖数: 373 | 2 深度优先或者广度优先搜索都可以吧
唯一特别的，可能是每次开始搜索时，给搜索编个号
比如第一次从[0][0]开始搜索，把自己能流到，以及能流到自己的格子都标记为1号
直到搜索完成
然后找到另一块还没有标记为1的格子，标记为2，再从他开始搜索
直到所有格子都有标记了，就结束了 |
|
