The problem presents us with a grid consisting of 0’s (water) and 1’s (land). We are required to find total number of islands in the grid. An island is a collection of 1’s next to each other - either vertically or horizontally - no, diagonal relations. But as part of a homework/revision once you solve this problem, try solving it but include diagonal relations too - it could be solved using just minor changes.
To come up with a solution to this, an overview intuition is that when we arrive at a 1 we need to find out if there is one more 1 right next to it. That includes one position up, down, left and right. If there exists a 1, do the above check again on this 1 and so on - UNTIL we arrive at a 1 that has only 0’s around it.
You would have noticed that this is looks like a pair of base case and a sub-problem. The base case is to stop when you find a 1 with 0’s around it, and the sub-problem is to keep on finding a 1 in any direction (apart from the 1 we have already visited - for this we can use another array of same dimensions that of our grid, so we can remember which 1 have been visited/pending). By performing Depth-First Search (DFS) on our grid we can find a singular island. We can also obtain it’s area if needed - it’s not needed in this problem, consider it a follow-up question ; )
Code:
class Solution {
public:
void search(vector<vector<char>>& grid, vector<vector<bool>>& visited, int i, int j) {
if (i<0 || i>=grid.size() || j<0 || j>=grid[i].size()) return;
if (grid[i][j] == '1' && !visited[i][j]) { // checking visited[i][j] will help us ignore the 1's we have already visited
visited[i][j] = true;
search(grid,visited,i-1,j);
search(grid,visited,i+1,j);
search(grid,visited,i,j-1);
search(grid,visited,i,j+1);
}
}
void populate_by_false(vector<vector<bool>>& visited, int m, int n) {
visited.resize(m, vector<bool>(n, false));
}
int numIslands(vector<vector<char>>& grid) {
vector<vector<bool>> visited;
populate_by_false(visited,grid.size(),grid[0].size());
int count=0;
for (int i=0;i<grid.size();++i) {
for (int j=0;j<grid[0].size();++j) {
if (grid[i][j] == '1' && !visited[i][j]) {
search(grid, visited, i, j);
++count;
}
}
}
return count;
}
};We iterate through our 2-D grid, and when we encounter a 1 that also isn’t visited (we get this by checking if visited[i][j] == true/false), we call our search() function which will recursively visit all surrounding neighbors.
— A