- /**
- * Copyright (c) 2013, Omega Coleman <omegacoleman@gmail.com>
- * All rights reserved.
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * * Neither the name of Omega Coleman nor the names of its contributors
- * may be used to endorse or promote products derived from this software
- * without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY OMEGA COLEMAN AND CONTRIBUTORS "AS IS" AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
- * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
- * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- **/
- /**
- 题目如下:
- 来源:https://code.google.com/codejam/contest/90101/dashboard#s=p1
- 版权:
- All problem statements, input data and contest analyses are licensed under
- the Creative Commons Attribution License.
- 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 containing W 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
- 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
- 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).
- **/
- #include <iostream>
- #include <vector>
- // 从v中找到最西北的空白单元'-'。
- bool find_first_empty(const std::vector<std::vector<char> >& v, int& dest_y, int& dest_x)
- {
- for (dest_y = 0; dest_y < (int)v.size(); dest_y ++)
- {
- for(dest_x = 0; dest_x < (int)v[dest_y].size(); dest_x ++)
- {
- if (v[dest_y][dest_x] == '-')
- {
- return true;
- }
- }
- }
- return false;
- }
- // 得到map中y行x列的海拔,OOR则返回false。
- bool get_altit(const std::vector<std::vector<int> >& map, const int y, const int x, int& target)
- {
- if ((y >= 0) && (y < (int)map.size()))
- {
- if ((x >= 0) && (x < (int)map[y].size()))
- {
- target = map[y][x];
- return true;
- }
- }
- return false;
- }
- // 检测y行x列是否已经填入字母。
- bool filled(const std::vector<std::vector<char> >& o_map, const int y, const int x)
- {
- if ((y >= 0) && (y < (int)o_map.size()))
- {
- if ((x >= 0) && (x < (int)o_map[y].size()))
- {
- return o_map[y][x] != '-';
- }
- }
- return true;
- }
- // 将(x, y)处放水,把按规则流动一个单位后的(x, y)写入。
- bool flow(const std::vector<std::vector<int> >& map, int& y, int& x)
- {
- int lowest, curr;
- int lowest_y, lowest_x;
- int curr_neigh;
- if (!get_altit(map, y, x, lowest))
- {
- return false;
- }
- curr = lowest;
- lowest_y = y;
- lowest_x = x;
- if (get_altit(map, y - 1, x, curr_neigh))
- {
- if (curr_neigh < lowest)
- {
- lowest = curr_neigh;
- lowest_y = y - 1;
- lowest_x = x;
- }
- }
- if (get_altit(map, y, x - 1, curr_neigh))
- {
- if (curr_neigh < lowest)
- {
- lowest = curr_neigh;
- lowest_y = y;
- lowest_x = x - 1;
- }
- }
- if (get_altit(map, y, x + 1, curr_neigh))
- {
- if (curr_neigh < lowest)
- {
- lowest = curr_neigh;
- lowest_y = y;
- lowest_x = x + 1;
- }
- }
- if (get_altit(map, y + 1, x, curr_neigh))
- {
- if (curr_neigh < lowest)
- {
- lowest = curr_neigh;
- lowest_y = y + 1;
- lowest_x = x;
- }
- }
- if (lowest != curr)
- {
- y = lowest_y;
- x = lowest_x;
- return true;
- }
- return false;
- }
- // 测试n处若放水,水能否流动到(x, y)。
- // o_map纯属加速之用。
- bool oppo_flow(const std::vector<std::vector<int> >& map, const std::vector<std::vector<char> >& o_map, const int y, const int x, int n_y, int n_x)
- {
- if(! filled(o_map, n_y, n_x))
- {
- if (flow(map, n_y, n_x))
- {
- if ((n_y == y) && (n_x == x))
- {
- return true;
- }
- }
- }
- return false;
- }
- // 在(x, y)放水,将流经之处全部在o_map上用ch标出。
- void mega_flow(const std::vector<std::vector<int> >& map, std::vector<std::vector<char> >& o_map, const int y, const int x, const char ch)
- {
- int curr_x, curr_y;
- curr_y = y;
- curr_x = x;
- o_map[y][x] = ch;
- if (flow(map, curr_y, curr_x))
- {
- mega_flow(map, o_map, curr_y, curr_x, ch);
- }
- if(oppo_flow(map, o_map, y, x, y - 1, x))
- {
- mega_flow(map, o_map, y - 1, x, ch);
- }
- if(oppo_flow(map, o_map, y, x, y + 1, x))
- {
- mega_flow(map, o_map, y + 1, x, ch);
- }
- if(oppo_flow(map, o_map, y, x, y, x+1))
- {
- mega_flow(map, o_map, y, x + 1, ch);
- }
- if(oppo_flow(map, o_map, y, x, y, x - 1))
- {
- mega_flow(map, o_map, y, x - 1, ch);
- }
- }
- int main()
- {
- int T, case_num;
- std::cin >> T;
- for (case_num = 0; case_num < T; case_num++)
- {
- int h, w, i, j;
- std::vector<std::vector<int> > map;
- std::vector<std::vector<char> > o_map;
- std::cin >> h >> w;
- // 将等高地形数据读入map。
- // o_map初始为全'-'的等大地图。
- for(i = 0; i < h; i++)
- {
- map.push_back(std::vector<int>());
- o_map.push_back(std::vector<char>());
- for (j = 0; j < w; j++)
- {
- int curr_altit;
- std::cin >> curr_altit;
- map.back().push_back(curr_altit);
- o_map.back().push_back('-');
- }
- }
- // 用从a开始的字母把流域一块块标出。
- char curr_char = 'a';
- int curr_y, curr_x;
- while (find_first_empty(o_map, curr_y, curr_x))
- {
- mega_flow(map, o_map, curr_y, curr_x, curr_char);
- curr_char++;
- }
- // 打印~
- std::cout << "Case #" << case_num + 1 << ":" << std::endl;
- for(i = 0; i < h; i++)
- {
- for (j = 0; j < w; j++)
- {
- std::cout << o_map[i][j] << ' ';
- }
- std::cout << std::endl;
- }
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/030420149224.html
来源: http://www.codesnippet.cn/detail/030420149224.html