• API
• FAQ
• Tools
• Archive
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.

Top