You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
99 lines
3.3 KiB
C++
99 lines
3.3 KiB
C++
/* Problem source: https://leetcode.com/problems/number-of-islands/
|
|
*/
|
|
|
|
#include <iostream>
|
|
#include <limits>
|
|
#include <stack>
|
|
#include <unordered_set>
|
|
#include <vector>
|
|
|
|
struct matrix_location {
|
|
unsigned c; // column
|
|
unsigned r; // row
|
|
bool operator==(const matrix_location &other) const {
|
|
return c == other.c && r == other.r;
|
|
};
|
|
};
|
|
|
|
class matrix_location_hash {
|
|
private:
|
|
unsigned n_cols;
|
|
|
|
public:
|
|
matrix_location_hash(const unsigned num_of_cols, const unsigned num_of_rows)
|
|
: n_cols(num_of_cols) {
|
|
if (num_of_rows >
|
|
std::numeric_limits<unsigned long long>::max() / num_of_cols)
|
|
throw "Grid too big, cannot represent all cells with unique number for "
|
|
"efficient hashing";
|
|
};
|
|
std::size_t operator()(const matrix_location &m) const {
|
|
unsigned long long cell = m.c + m.r * n_cols;
|
|
return std::hash<unsigned long long>()(cell);
|
|
}
|
|
};
|
|
|
|
unsigned num_of_islands(const std::vector<std::vector<char>> &grid) {
|
|
unsigned n_islands = 0;
|
|
matrix_location_hash ml_hash(grid.size(),
|
|
grid[0].size()); // FIXME: potential seg fault
|
|
std::unordered_set<matrix_location, matrix_location_hash> unexplored_land(
|
|
10, ml_hash);
|
|
for (unsigned i = 0, columns = grid.size(); i < columns; i++) {
|
|
for (unsigned j = 0, rows = grid[i].size(); j < rows; j++) {
|
|
if (grid[i][j] == '0') {
|
|
} else if (grid[i][j] == '1') {
|
|
unexplored_land.insert({i, j});
|
|
} else {
|
|
throw "Input grid cannot have elements other than '0' or '1'";
|
|
}
|
|
}
|
|
}
|
|
while (unexplored_land.size()) {
|
|
for (auto &loc : unexplored_land) {
|
|
std::stack<matrix_location> sub_explore({loc});
|
|
bool island_added = false;
|
|
while (!sub_explore.empty()) {
|
|
matrix_location curr_loc = sub_explore.top();
|
|
matrix_location above = {curr_loc.c - 1, curr_loc.r},
|
|
left = {curr_loc.c, curr_loc.r - 1},
|
|
right = {curr_loc.c, curr_loc.r + 1},
|
|
below = {curr_loc.c + 1, curr_loc.r};
|
|
sub_explore.pop();
|
|
if (!island_added) {
|
|
n_islands++;
|
|
island_added = true;
|
|
}
|
|
if (unexplored_land.count(above)) {
|
|
sub_explore.push(above);
|
|
}
|
|
if (unexplored_land.count(left)) {
|
|
sub_explore.push(left);
|
|
}
|
|
if (unexplored_land.count(right)) {
|
|
sub_explore.push(right);
|
|
}
|
|
if (unexplored_land.count(below)) {
|
|
sub_explore.push(below);
|
|
}
|
|
unexplored_land.erase(curr_loc);
|
|
}
|
|
break;
|
|
}
|
|
}
|
|
return n_islands;
|
|
}
|
|
|
|
int main() {
|
|
const std::vector<std::vector<char>> grid = {{'1', '1', '1', '1', '0'},
|
|
{'1', '1', '0', '1', '0'},
|
|
{'1', '1', '0', '0', '0'},
|
|
{'0', '0', '0', '0', '0'}},
|
|
grid2 = {{'1', '1', '0', '0', '0'},
|
|
{'1', '1', '0', '0', '0'},
|
|
{'0', '0', '1', '0', '0'},
|
|
{'0', '0', '0', '1', '1'}};
|
|
std::cout << num_of_islands(grid) << '\n' << num_of_islands(grid2) << "\n";
|
|
return 0;
|
|
}
|