SHARE
TWEET

Untitled

bbescos Feb 18th, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. // I use this Point struct rather than a pair<int, int> to make it shortes
  8. // Point rather than pair<int, int> to initialize
  9. // Point.x and Point.y rather than Point.first and Point.second
  10. struct Point {
  11.     int x;
  12.     int y;
  13.     Point (int x, int y): x(x), y(y) {}
  14. };
  15.  
  16. // This function is to check if a Point's coordinates are within the map
  17. bool InMap(const vector<vector<int>>& map, const Point& current) {
  18.    
  19.     return (current.x >= 0 && current.x < map.size() && current.y >= 0 && current.y < map[0].size());
  20. }
  21.  
  22. // This function returns the number of connected elements to {0,0} equal to 1 within map
  23. int NumElem(const vector<vector<int>>& map) {
  24.    
  25.     int ans = 0;
  26.    
  27.     vector<vector<bool>> visited_map(map.size(), vector<bool> (map[0].size(), false));
  28.    
  29.     vector<Point> neighbors_map = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
  30.    
  31.     queue<Point> qPoints;
  32.     qPoints.push({0, 0});
  33.     visited_map[0][0] = true;
  34.    
  35.     while (!qPoints.empty()) {
  36.         Point current = qPoints.front();
  37.         qPoints.pop();
  38.         ++ans;
  39.        
  40.         for (int i = 0; i < 4; ++i) {
  41.             Point neighbor({current.x + neighbors_map[i].x, current.y + neighbors_map[i].y});
  42.             if (InMap(map, neighbor) && map[neighbor.x][neighbor.y] == 1 && !visited_map[neighbor.x][neighbor.y]) {
  43.                 visited_map[neighbor.x][neighbor.y] = true;
  44.                 qPoints.push(neighbor);
  45.             }
  46.         }
  47.     }
  48.    
  49.     return ans;
  50. }
  51.  
  52. // This function sets visited_map to true for the elements connected to start within map
  53. void FloodFill(const vector<vector<int>>& map, vector<vector<bool>>& visited_map, const Point& start) {
  54.    
  55.     vector<Point> neighbors_map = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
  56.    
  57.     queue<Point> qPoints;
  58.     qPoints.push({start.x, start.y});
  59.     visited_map[start.x][start.y] = true;
  60.    
  61.     int val = map[start.x][start.y];
  62.    
  63.     while (!qPoints.empty()) {
  64.         Point current = qPoints.front();
  65.         qPoints.pop();
  66.        
  67.         for (int i = 0; i < 4; ++i) {
  68.             Point neighbor({current.x + neighbors_map[i].x, current.y + neighbors_map[i].y});
  69.             if (InMap(map, neighbor) && map[neighbor.x][neighbor.y] == val && !visited_map[neighbor.x][neighbor.y]) {
  70.                 visited_map[neighbor.x][neighbor.y] = true;
  71.                 qPoints.push(neighbor);
  72.             }
  73.         }
  74.     }
  75. }
  76.  
  77. // This function returns the number of islands within map
  78. // Problem when one island has a lake that has islands
  79. // These islands are counted. However they should not
  80. /*
  81. int NumIslands(const vector<vector<int>>& map) {
  82.    
  83.     vector<vector<bool>> visited_map(map.size(), vector<bool> (map[0].size(), false));
  84.     int ans = 0;
  85.    
  86.     for (int i = 0; i < map.size(); ++i) {
  87.         for (int j = 0; j < map[0].size(); ++j) {
  88.             if (map[i][j] == 1 && visited_map[i][j] == false) {
  89.                 Point current(i,j);
  90.                 FloodFill(map, visited_map, current);
  91.                 ++ans;
  92.             }
  93.         }
  94.     }
  95.    
  96.     return ans;
  97. }
  98. */
  99. // This function returns the number of islands within map
  100. // It does not count the lake's islands
  101. int NumIslands(const vector<vector<int>>& map) {
  102.    
  103.     vector<Point> neighbors_map = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
  104.    
  105.     vector<vector<bool>> visited_map(map.size(), vector<bool> (map[0].size(), false));
  106.     FloodFill(map, visited_map, {0,0});
  107.     int ans = 0;
  108.    
  109.     for (int i = 0; i < map.size(); ++i) {
  110.         for (int j = 0; j < map[0].size(); ++j) {
  111.             bool neighbor_is_sea = false;
  112.             int k = 0;
  113.             while (!neighbor_is_sea && k < 4) {
  114.                 Point neighbor({i + neighbors_map[k++].x, j + neighbors_map[k++].y});
  115.                 neighbor_is_sea = InMap(map, neighbor) && visited_map[neighbor.x][neighbor.y];
  116.             }
  117.  
  118.             if (neighbor_is_sea && map[i][j] == 1 && !visited_map[i][j]) {
  119.                 Point current(i,j);
  120.                 FloodFill(map, visited_map, current);
  121.                 ++ans;
  122.             }
  123.         }
  124.     }
  125.    
  126.     return ans;
  127. }
  128.  
  129. int main()
  130. {
  131.     vector<vector<int>> map1 = {{0, 0, 0, 0, 0, 0},
  132.                             {0, 1, 1, 0, 1, 0},
  133.                             {0, 1, 1, 0, 1, 0},
  134.                             {0, 0, 0, 0, 0, 0},
  135.                             {0, 0, 0, 0, 1, 0}};
  136.                            
  137.     vector<vector<int>> map2 = {{0, 0, 0, 0, 0, 0, 0},
  138.                             {0, 1, 1, 1, 1, 1, 0},
  139.                             {0, 1, 0, 0, 0, 1, 0},
  140.                             {0, 1, 0, 1, 0, 1, 0},
  141.                             {0, 1, 0, 0, 0, 1, 0},
  142.                             {0, 1, 1, 1, 1, 1, 0},
  143.                             {0, 0, 0, 0, 0, 0, 0}};
  144.  
  145.     std::cout << NumIslands(map1) << std::endl;
  146.     std::cout << NumIslands(map2) << std::endl;
  147.     return 0;
  148. }
RAW Paste Data
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
 
Top