Advertisement
Guest User

Untitled

a guest
May 20th, 2018
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. uint32_t findRegionSize(
  7.     std::pair<int, int> curElPos,
  8.     const std::vector<std::vector<int>>& grid,
  9.     std::set<std::pair<int, int>>& elementsOfCurRegion
  10. )
  11. {
  12.     uint32_t size = 0;
  13.     elementsOfCurRegion.insert(curElPos);
  14.  
  15.     auto elPos = std::make_pair(curElPos.first, curElPos.second + 1);
  16.     if (elPos.second < grid.front().size()
  17.         && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
  18.         if (grid[elPos.first][elPos.second]) {
  19.             elementsOfCurRegion.insert(elPos);
  20.  
  21.             size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
  22.        }
  23.     }
  24.  
  25.     elPos = std::make_pair(curElPos.first, curElPos.second - 1);
  26.     if (elPos.second >= 0
  27.         && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
  28.         if (grid[elPos.first][elPos.second]) {
  29.             elementsOfCurRegion.insert(elPos);
  30.  
  31.             size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
  32.         }
  33.     }
  34.  
  35.     elPos = std::make_pair(curElPos.first + 1, curElPos.second);
  36.     if (elPos.first < grid.size()
  37.         && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
  38.         if (grid[elPos.first][elPos.second]) {
  39.             elementsOfCurRegion.insert(elPos);
  40.  
  41.             size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
  42.         }
  43.     }
  44.  
  45.     elPos = std::make_pair(curElPos.first - 1, curElPos.second);
  46.     if (elPos.first >= 0
  47.         && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
  48.         if (grid[elPos.first][elPos.second]) {
  49.             elementsOfCurRegion.insert(elPos);
  50.  
  51.             size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
  52.         }
  53.     }
  54.  
  55.     elPos = std::make_pair(curElPos.first - 1, curElPos.second - 1);
  56.     if (elPos.first >= 0
  57.         && elPos.second >= 0
  58.         && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
  59.         if (grid[elPos.first][elPos.second]) {
  60.             elementsOfCurRegion.insert(elPos);
  61.  
  62.             size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
  63.         }
  64.     }
  65.  
  66.     elPos = std::make_pair(curElPos.first - 1, curElPos.second + 1);
  67.     if (elPos.first >= 0
  68.         && elPos.second < grid.front().size()
  69.         && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
  70.         if (grid[elPos.first][elPos.second]) {
  71.             elementsOfCurRegion.insert(elPos);
  72.  
  73.             size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
  74.         }
  75.     }
  76.  
  77.     elPos = std::make_pair(curElPos.first + 1, curElPos.second - 1);
  78.     if (elPos.first < grid.size()
  79.         && elPos.second >= 0
  80.         && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
  81.         if (grid[elPos.first][elPos.second]) {
  82.             elementsOfCurRegion.insert(elPos);
  83.  
  84.             size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
  85.         }
  86.     }
  87.  
  88.     elPos = std::make_pair(curElPos.first + 1, curElPos.second + 1);
  89.     if (elPos.first < grid.size()
  90.         && elPos.second < grid.front().size()
  91.         && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
  92.         if (grid[elPos.first][elPos.second]) {
  93.             elementsOfCurRegion.insert(elPos);
  94.  
  95.             size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
  96.         }
  97.     }
  98.  
  99.     return size;
  100. }
  101.  
  102.  
  103. uint32_t findSizeOfMaxRegion(const std::vector<std::vector<int>>& grid)
  104. {
  105.     uint32_t size =  0;
  106.     std::set<std::pair<int, int>> passedElements;
  107.     std::set<std::pair<int, int>> elementsOfCurRegion;
  108.  
  109.     for (auto rowIt = grid.begin(); rowIt != grid.end(); ++rowIt) {
  110.         for (auto columnIt = rowIt->begin(); columnIt != rowIt->end(); ++columnIt) {
  111.             if (*columnIt) {
  112.                 std::pair<int, int> elementPosition(
  113.                     rowIt - grid.begin(),
  114.                     columnIt - rowIt->begin()
  115.                 );
  116.                 if (passedElements.find(elementPosition) == passedElements.end()) {
  117.                     elementsOfCurRegion.insert(elementPosition);
  118.                     size += 1 + findRegionSize(elementPosition, grid, elementsOfCurRegion);
  119.  
  120.                     passedElements.insert(elementsOfCurRegion.begin(), elementsOfCurRegion.end());
  121.                     elementsOfCurRegion.clear();
  122.                 }
  123.             }
  124.         }
  125.     }
  126.  
  127.     return size;
  128. }
  129.  
  130.  
  131. int main()
  132. {
  133.     int n;
  134.     cin >> n;
  135.     cin.ignore(numeric_limits<streamsize>::max(), '\n');
  136.  
  137.     int m;
  138.     cin >> m;
  139.     cin.ignore(numeric_limits<streamsize>::max(), '\n');
  140.  
  141.     vector<vector<int>> grid(n);
  142.     for (int i = 0; i < n; i++) {
  143.         grid[i].resize(m);
  144.  
  145.         for (int j = 0; j < m; j++) {
  146.             cin >> grid[i][j];
  147.         }
  148.  
  149.         cin.ignore(numeric_limits<streamsize>::max(), '\n');
  150.  
  151.         std::cout << findSizeOfMaxRegion(grid);
  152.     }
  153.  
  154.     return 0;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement