Code Review Asked on November 13, 2021
I’m posting my code for a LeetCode problem. If you’d like to review, please do so. Thank you for your time!
Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number
of islands. An island is surrounded by water and is formed by
connecting adjacent lands horizontally or vertically. You may assume
all four edges of the grid are all surrounded by water.Example 1:
Input: 11110 11010 11000 00000 Output: 1Example 2:
Input: 11000 11000 00100 00011 Output: 3
#include <vector>
class Solution {
public:
std::size_t numIslands(std::vector<std::vector<char>>& grid) {
std::size_t row_length = grid.size();
if (!row_length) {
return 0;
}
std::size_t col_length = grid[0].size();
std::size_t islands = 0;
// Runs depth first search for every cell
for (std::size_t row = 0; row < row_length; row++) {
for (std::size_t col = 0; col < col_length; col++) {
if (grid[row][col] == '1') {
islands++;
depth_first_search(grid, row, col, row_length, col_length);
}
}
}
return islands;
}
private:
void depth_first_search(std::vector<std::vector<char>>& grid, const std::size_t row, const std::size_t col, const std::size_t row_length, const std::size_t col_length) {
// Checks for grid boundaries and '0' cells
if (row < 0 || row >= row_length || col < 0 || col >= col_length || grid[row][col] == '0') {
return;
}
grid[row][col] = '0';
// Recurse in 4 directions of grid
depth_first_search(grid, row + 1, col, row_length, col_length);
depth_first_search(grid, row - 1, col, row_length, col_length);
depth_first_search(grid, row, col + 1, row_length, col_length);
depth_first_search(grid, row, col - 1, row_length, col_length);
}
};
class Solution {
private:
void dfs(vector<vector<char>>& grid, int r, int c) {
int nr = grid.size();
int nc = grid[0].size();
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
}
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
};
On LeetCode, there is a class usually named Solution with one or more public functions which we are not allowed to rename.
depth_first_search()One improvement your solution has over LeetCode's is that you move the grid boundary check into depth_first_search(). However, you can do more, by having it return whether you are starting on an island or in the ocean:
bool depth_first_search(...) {
// Checks for grid boundaries and '0' cells
if (...)
return false;
// We are on an island, recurse
...
return true;
}
Then, the loop inside numIslands() can be simplified:
for (std::size_t row = 0; row < row_length; row++)
for (std::size_t col = 0; col < col_length; col++)
islands += depth_first_search(grid, row, col, row_length, col_length);
While depth_first_search() does iterate in a depth-first fashion, it is not search for anything. Rather, it is implementing a flood fill algorithm. But here we use it to remove an island. If it also performs a check to see if there is an island at the given position, I would name it check_and_remove_island(). As Emily L. mentions, a function name that reads like foo_and_bar() is usually a hint that it should be split into a foo() and bar(). If you want to go that way, I suggest you make it so you can write the following code:
if (is_island(grid, row, col)) {
islands++;
remove_island(grid, row, col);
}
I don't think it's that useful to store the sizes into separate variables, and to pass them explicitly to depth_first_search(). This information can always easily be gotten from the variable grid. This also gets rid of the check for an empty grid:
std::size_t numIslands(std::vector<std::vector<char>>& grid) {
size_t islands{};
for(std::size_t row = 0; row < grid.size(); row++)
for (std::size_t col = 0; col < grid[row].size(); col++)
islands += check_and_remove_island(grid, row, col);
return islands;
}
You have to modify depth_first_search() to match of course.
Answered by G. Sliepen on November 13, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP