https://code.google.com/codejam/contest/90101/dashboard#s=p1
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.
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'.)
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 containingW integers, from west to east, specifying the altitudes of the cells.
Output
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.
Limits
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.
Sample
| Input |
Output |
5 |
Case #1: |
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).
Solution:
int H, W;
vector<vector<int>>mmap; pair<int, int> r_cell (int X, int Y)
{
int alt = mmap[X][Y];
int min_alt = alt;
int tX, tY, maX = -, maY = -; tX = X - ; tY = Y - ;
if (tX >= && tX < H && tY >= && tY < W)
if (mmap[tX][tY] < min_alt) {
min_alt = mmap[tX][tY];
maX = tX; maY = tY;
} tX = X - ; tY = Y - ;
if (tX >= && tX < H && tY >= && tY < W)
if (mmap[tX][tY] < min_alt) {
min_alt = mmap[tX][tY];
maX = tX; maY = tY;
} tX = X - ; tY = Y + ;
if (tX >= && tX < H && tY >= && tY < W)
if (mmap[tX][tY] < min_alt) {
min_alt = mmap[tX][tY];
maX = tX; maY = tY;
} tX = X + ; tY = Y - ;
if (tX >= && tX < H && tY >= && tY < W)
if (mmap[tX][tY] < min_alt) {
min_alt = mmap[tX][tY];
maX = tX; maY = tY;
} if ((min_alt) < alt) {
return r_cell(maX, maY);
} else {
return pair<int, int>(X, Y);
} } map<pair<int, int>, char> solve()
{ map<pair<int, int>, vector<pair<int, int>>>sinks;
map<pair<int, int>, char>sinklabel;
map<pair<int, int>, char>label;
char b_label = 'a' - ; for (int h = ; h < H; h++) {
for (int w = ; w < W; w++) {
pair<int, int> cell = r_cell(h, w); if (!sinks.count(pair<int, int>(cell.first, cell.second))) {
b_label++; // new sink
sinks.insert(pair<pair<int, int>, vector<pair<int, int>>>(pair<int, int>(cell.first, cell.second), vector<pair<int, int>>()));
sinklabel.insert(pair<pair<int, int>, char>(pair<int, int>(cell.first, cell.second), b_label));
} // add to existing sink
sinks.at(pair<int, int>(cell.first, cell.second)).push_back(pair<int, int>(h, w));
label.insert(pair<pair<int, int>, char>(pair<int, int>(h, w), sinklabel.at(pair<int, int>(cell.first, cell.second))));
}
} return label;
} int main()
{ freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout); int T;
scanf("%d\n", &T);
if (!T) {
cerr << "Check input!" << endl;
exit();
} for (int t = ; t <= T; t++) {
scanf("%d %d\n", &H, &W); // map
mmap.clear();
int alt;
for (int h = ; h < H; h++) {
vector<int> row;
for (int w = ; w < W; w++) {
scanf("%d", &alt);
row.push_back(alt);
}
mmap.push_back(row);
} auto result = solve();
printf("Case #%d:\n", t); for (int h = ; h < H; h++) {
for (int w = ; w < W; w++) {
printf("%c ", result.at(pair<int, int>(h, w)));
}
printf("\n");
}
} fclose(stdin);
fclose(stdout);
return ;
}