DFS of 2D array with only k steps

  2d, c++, depth-first-search

I have to do a DFS on a 2D array but not entirely. It should happen only for k steps before terminating. That means starting at some particular position the DFS should work for a combination of left, right, up and down direction for only k steps. For each of the K steps for a particular position I am incrementing values in the matrix. Here is my code for DFS –

void component(vector<vector<int>>& grid, vector<vector<int> >&visited, int i,int j, int k){
    
    if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size() || visited[i][j]==1 || k < 0){
        return;
    }
    visited[i][j] = 1;
    grid[i][j]++;
    component(grid,visited,i,j-1,k-1);
    component(grid,visited,i+1,j,k-1);
    component(grid,visited,i,j+1,k-1);
    component(grid,visited,i-1,j,k-1);
}

The Grid looks like this before DFS call –

vector< vector<int> > grid= {{0,0,0,1}, {0,1,0,0}, {0,0,1,0}, {1,0,0,0}, {0,0,0,0}};

I am calling the function like this component(grid,visited,row,col) where row and col are indexes for row and col where 1 is found in the grid. (Actually I am saving all the positions having 1 in the grid and then updating them back again once a DFS call is complete for a 1 – This makes sure that I dont skip any 1 for the grid) I am not getting the desired output for my DFS function. Please help me find out what is wrong.

Source: Windows Questions C++

LEAVE A COMMENT