Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- uint32_t findRegionSize(
- std::pair<int, int> curElPos,
- const std::vector<std::vector<int>>& grid,
- std::set<std::pair<int, int>>& elementsOfCurRegion
- )
- {
- uint32_t size = 0;
- elementsOfCurRegion.insert(curElPos);
- auto elPos = std::make_pair(curElPos.first, curElPos.second + 1);
- if (elPos.second < grid.front().size()
- && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
- if (grid[elPos.first][elPos.second]) {
- elementsOfCurRegion.insert(elPos);
- size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
- }
- }
- elPos = std::make_pair(curElPos.first, curElPos.second - 1);
- if (elPos.second >= 0
- && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
- if (grid[elPos.first][elPos.second]) {
- elementsOfCurRegion.insert(elPos);
- size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
- }
- }
- elPos = std::make_pair(curElPos.first + 1, curElPos.second);
- if (elPos.first < grid.size()
- && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
- if (grid[elPos.first][elPos.second]) {
- elementsOfCurRegion.insert(elPos);
- size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
- }
- }
- elPos = std::make_pair(curElPos.first - 1, curElPos.second);
- if (elPos.first >= 0
- && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
- if (grid[elPos.first][elPos.second]) {
- elementsOfCurRegion.insert(elPos);
- size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
- }
- }
- elPos = std::make_pair(curElPos.first - 1, curElPos.second - 1);
- if (elPos.first >= 0
- && elPos.second >= 0
- && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
- if (grid[elPos.first][elPos.second]) {
- elementsOfCurRegion.insert(elPos);
- size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
- }
- }
- elPos = std::make_pair(curElPos.first - 1, curElPos.second + 1);
- if (elPos.first >= 0
- && elPos.second < grid.front().size()
- && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
- if (grid[elPos.first][elPos.second]) {
- elementsOfCurRegion.insert(elPos);
- size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
- }
- }
- elPos = std::make_pair(curElPos.first + 1, curElPos.second - 1);
- if (elPos.first < grid.size()
- && elPos.second >= 0
- && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
- if (grid[elPos.first][elPos.second]) {
- elementsOfCurRegion.insert(elPos);
- size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
- }
- }
- elPos = std::make_pair(curElPos.first + 1, curElPos.second + 1);
- if (elPos.first < grid.size()
- && elPos.second < grid.front().size()
- && elementsOfCurRegion.find(elPos) == elementsOfCurRegion.end()) {
- if (grid[elPos.first][elPos.second]) {
- elementsOfCurRegion.insert(elPos);
- size += 1 + findRegionSize(elPos, grid, elementsOfCurRegion);
- }
- }
- return size;
- }
- uint32_t findSizeOfMaxRegion(const std::vector<std::vector<int>>& grid)
- {
- uint32_t size = 0;
- std::set<std::pair<int, int>> passedElements;
- std::set<std::pair<int, int>> elementsOfCurRegion;
- for (auto rowIt = grid.begin(); rowIt != grid.end(); ++rowIt) {
- for (auto columnIt = rowIt->begin(); columnIt != rowIt->end(); ++columnIt) {
- if (*columnIt) {
- std::pair<int, int> elementPosition(
- rowIt - grid.begin(),
- columnIt - rowIt->begin()
- );
- if (passedElements.find(elementPosition) == passedElements.end()) {
- elementsOfCurRegion.insert(elementPosition);
- size += 1 + findRegionSize(elementPosition, grid, elementsOfCurRegion);
- passedElements.insert(elementsOfCurRegion.begin(), elementsOfCurRegion.end());
- elementsOfCurRegion.clear();
- }
- }
- }
- }
- return size;
- }
- int main()
- {
- int n;
- cin >> n;
- cin.ignore(numeric_limits<streamsize>::max(), '\n');
- int m;
- cin >> m;
- cin.ignore(numeric_limits<streamsize>::max(), '\n');
- vector<vector<int>> grid(n);
- for (int i = 0; i < n; i++) {
- grid[i].resize(m);
- for (int j = 0; j < m; j++) {
- cin >> grid[i][j];
- }
- cin.ignore(numeric_limits<streamsize>::max(), '\n');
- std::cout << findSizeOfMaxRegion(grid);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement