This article is meant for For BEGINNERS who get confused while applying DFS on 2d Matrix and where to apply the base conditions. SInce there are various versions of DFS being used on leetcode let me break down these versions .
Variation 1: Combined Basecase
DFS(){
//Base Case
if boundary of Matrix is crossed
return
Process the current coordinate
//Recursive calls for Neighbours
DFS( right );
DFS( down );
DFS( left );
DFS( up );
} Variation 2: Separate Basecases before each recursive call
DFS(){
Process the current coordinate
Base Case for going right
DFS( right );
Base Case for going down
DFS( down );
Base Case for going left
DFS( left );
Base Case for going up
DFS( up );
} Variation 3 Direction Vector to explore neighbours
So people got tired of variation 2 as no one wants to write several base cases and recursive calls again and again
In some problems regarding 2d matrix we can move in all 8 directions which led to 8 recursive calls
So people came up with a direction vector approach to move in all directions
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
By practice you can directly write the direction vector intuitively too but for beginners its important to understand why are we doing this.
You can further extend this concept for all neighbours too
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}}
DFS(){
Process the current Coordinate
for(int i=0;i<4;i++){
//nx and ny are just the neighbours coordinates
int nx = dir[i][0]+current_x_coordinate
int ny = dir[i][1]+current y coordinate
BaseCase check on nx and ny we just calculated
DFS(nx, ny )
}
} Applying what we just learned on a problem
Lets Solve the problem 200. Number of Islands with all these variations for a better understanding
Variation 1
class Solution {
public:
void dfs(vector<vector<char>>& grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() ||
grid[i][j] != '1')
return;
grid[i][j] = '2';
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
};Variation 2
class Solution {
public:
void dfs(int i,int j,vector<vector<char>>& grid){
grid[i][j]=0;
int n=grid.size();
int m=grid[0].size();
if(i-1 >= 0 && grid[i-1][j] == '1')
dfs(i-1,j,grid);
if(i+1 < n && grid[i+1][j] == '1')
dfs(i+1,j,grid);
if(j-1 >= 0 && grid[i][j-1] == '1')
dfs(i,j-1,grid);
if(j+1 < m && grid[i][j+1] == '1')
dfs(i,j+1,grid);
}
int numIslands(vector<vector<char>>& grid) {
int n=grid.size();
int m=grid[0].size();
int ans=0;
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<m ; j++){
if(grid[i][j] == '1'){
ans++;
dfs(i,j,grid);
}
}
}
return ans;
}
};Variation 3
class Solution {
public:
int dirs[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
void dfs(vector<vector<char>>& grid, int r, int c) {
grid[r][c] = '0';
for (int k = 0; k < 4; k++) {
int rowdash = r + dirs[k][0];
int coldash = c + dirs[k][1];
if (rowdash >= 0 && coldash >= 0 && rowdash < grid.size() &&
coldash < grid[0].size() && grid[rowdash][coldash] == '1')
dfs(grid, rowdash, coldash);
}
}
int numIslands(vector<vector<char>>& grid) {
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') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
};