API tools faq
paste
Advertisement
coloriot

HA31_Water(7)

coloriot
Nov 15th, 2024
30
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.76 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. class Map {
  9. private:
  10.     int N, M;
  11.     vector<vector<int> > heights;
  12.     vector<vector<pair<int, int> > > sink;
  13.     int dx[4]; // Смещения по x для соседей
  14.     int dy[4]; // Смещения по y для соседей
  15.  
  16. public:
  17.     Map(int n, int m) {
  18.         N = n;
  19.         M = m;
  20.         heights.resize(N, vector<int>(M));
  21.         sink.resize(N, vector<pair<int, int> >(M, make_pair(-1, -1)));
  22.  
  23.         // Инициализация смещений: вверх, вниз, влево, вправо
  24.         dx[0] = -1; dy[0] = 0;  // Вверх
  25.         dx[1] = 1;  dy[1] = 0;  // Вниз
  26.         dx[2] = 0;  dy[2] = -1; // Влево
  27.         dx[3] = 0;  dy[3] = 1;  // Вправо
  28.     }
  29.  
  30.     void read_heights() {
  31.         for (int i = 0; i < N; ++i) {
  32.             for (int j = 0; j < M; ++j) {
  33.                 cin >> heights[i][j];
  34.             }
  35.         }
  36.     }
  37.  
  38.     bool is_valid(int x, int y) {
  39.         return x >= 0 && x < N && y >= 0 && y < M;
  40.     }
  41.  
  42.     pair<int, int> flow(int x, int y) {
  43.         if (sink[x][y].first != -1) {
  44.             return sink[x][y];
  45.         }
  46.  
  47.         // Маркируем ячейку как обрабатываемую
  48.         sink[x][y] = make_pair(-2, -2);
  49.  
  50.         // Список клеток текущего региона
  51.         vector<pair<int, int> > region_cells;
  52.         stack<pair<int, int> > s;
  53.         vector<vector<bool> > visited(N, vector<bool>(M, false));
  54.  
  55.         s.push(make_pair(x, y));
  56.  
  57.         while (!s.empty()) {
  58.             pair<int, int> current = s.top();
  59.             s.pop();
  60.             int cx = current.first;
  61.             int cy = current.second;
  62.  
  63.             if (visited[cx][cy]) {
  64.                 continue;
  65.             }
  66.             visited[cx][cy] = true;
  67.             region_cells.push_back(make_pair(cx, cy));
  68.  
  69.             for (int dir = 0; dir < 4; ++dir) {
  70.                 int nx = cx + dx[dir];
  71.                 int ny = cy + dy[dir];
  72.  
  73.                 if (is_valid(nx, ny) && heights[nx][ny] == heights[cx][cy]) {
  74.                     s.push(make_pair(nx, ny));
  75.                 }
  76.             }
  77.         }
  78.  
  79.         // Поиск соседей с меньшей высотой
  80.         pair<int, int> min_neighbor = make_pair(-1, -1);
  81.         int min_height = 10001; // Максимальная высота + 1
  82.  
  83.         for (size_t i = 0; i < region_cells.size(); ++i) {
  84.             int cx = region_cells[i].first;
  85.             int cy = region_cells[i].second;
  86.  
  87.             for (int dir = 0; dir < 4; ++dir) {
  88.                 int nx = cx + dx[dir];
  89.                 int ny = cy + dy[dir];
  90.  
  91.                 int neighbor_height;
  92.                 if (is_valid(nx, ny)) {
  93.                     neighbor_height = heights[nx][ny];
  94.                 } else {
  95.                     neighbor_height = 10001; // Высота за пределами карты
  96.                 }
  97.  
  98.                 if (neighbor_height < heights[cx][cy]) {
  99.                     if (neighbor_height < min_height) {
  100.                         min_height = neighbor_height;
  101.                         min_neighbor = make_pair(nx, ny);
  102.                     }
  103.                 }
  104.             }
  105.         }
  106.  
  107.         pair<int, int> sink_coord;
  108.         if (min_neighbor.first != -1 && is_valid(min_neighbor.first, min_neighbor.second)) {
  109.             sink_coord = flow(min_neighbor.first, min_neighbor.second);
  110.         } else if (min_neighbor.first != -1) {
  111.             // Если сосед вне границ карты (высота 10001), то вода не может утечь
  112.             sink_coord = make_pair(-1, -1);
  113.         } else {
  114.             // Это место является водосбором
  115.             sink_coord = make_pair(x, y);
  116.         }
  117.  
  118.         // Устанавливаем sink для всех клеток региона
  119.         for (size_t i = 0; i < region_cells.size(); ++i) {
  120.             int cx = region_cells[i].first;
  121.             int cy = region_cells[i].second;
  122.             sink[cx][cy] = sink_coord;
  123.         }
  124.  
  125.         return sink[x][y];
  126.     }
  127.  
  128.     int calculate_min_drains() {
  129.         set<pair<int, int> > unique_sinks;
  130.  
  131.         for (int i = 0; i < N; ++i) {
  132.             for (int j = 0; j < M; ++j) {
  133.                 pair<int, int> sink_coord = flow(i, j);
  134.                 if (sink_coord == make_pair(i, j)) {
  135.                     unique_sinks.insert(sink_coord);
  136.                 }
  137.             }
  138.         }
  139.  
  140.         return unique_sinks.size();
  141.     }
  142. };
  143.  
  144. int main() {
  145.     int N, M;
  146.     cin >> N >> M;
  147.  
  148.     Map terrain(N, M);
  149.     terrain.read_heights();
  150.  
  151.     int result = terrain.calculate_min_drains();
  152.     cout << result << endl;
  153.  
  154.     return 0;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!