CODEWITHSUNDEEP
c++algorithmdynamic-programmingdepth-first-searchbacktracking
user3182811
user3182811

Reputation: 115

Count number of paths in a grid using dynamic programming?

A robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down, Where some of cells are dead i.e. robot can't enter in that cell .How many possible paths are there for the robot?
This can be solved using Backtracking but it's time complexity is too high .I had solved this problem using backtracking but it takes O(2^n) in worse case .

bool exist(bool a[][], int i, int j,int N){
        return i>=0 && j >=0 && i < N && j < N;
    }
    int search(bool  a[][], int i, int j,int N){
        if(!exist(a,i,j,N) || a[i][j] == 1)
            return 0; // no path here.
        if(i == N-1 && j == N - 1){
            return 1; // 1 path here.
        }
        a[i][j] = 1; // mark that we have seen this spot here
        int paths = 0; // introduce a counter...
        paths += search(a, i,j+1,N); // add the additional paths as we find them
        paths += search(a, i+1,j,N);
        a[i][j] = 0;
        return paths; // return the number of paths available from this point.
    }

Here cell with 1 represents dead cell.Is any way to reduce time complexity by using DFS or Dynamic programming e.t.c ?

Upvotes: 0

Views: 5712

Answers (3)

user4478738
user4478738

Reputation:

Let us assume the following 3x3 grid where 1 in the grids denotes the obstacle

[0, 0, 0]
[0, 1, 0]
[0, 0, 0]

The number of unique paths in this case is 2. We can use the dynamic programming approach to reduce time complexity find unique paths and here is the code for the same in C++

int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
       int m = obstacleGrid.size();
       int n = obstacleGrid[0].size();

    vector<vector<int> > arr(m,vector<int>(n,0));

    if (obstacleGrid[0][0]==1){return 0;}
    arr[0][0]=1;
    for (int i=1;i<m;i++){
        if (obstacleGrid[i][0]!=1){
            arr[i][0] = arr[i-1][0];
        }
    }
    for (int i=1;i<n;i++){
        if (obstacleGrid[0][i]!=1){
            arr[0][i] = arr[0][i-1];
        }
    }
    for (int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            if (obstacleGrid[i][j]!=1){
                arr[i][j] = arr[i][j-1] + arr[i-1][j];
            }
        }
    }   
    return arr[m-1][n-1];
}

The time complexity in this case is O(mn).

Upvotes: 0

justmscs
justmscs

Reputation: 756

Given a NxN grid, let ways[i][j] = number of possible paths from grid[0][0] to grid[i][j]

initialize grid[0][0] = 1

if grid[i][j] is dead, ways[i][j] = 0

else ways[i][j] = ways[i-1][j] + ways[i][j-1] (but be careful with the edge)

An example:

grid:(1 means dead)   ways:

0 0 1 0 0             1 1 0 0 0
0 0 0 0 0             1 2 2 2 2
0 1 0 0 1             1 0 2 4 0
1 0 0 0 0             0 0 2 6 6
0 0 0 0 0             0 0 2 8 14

I think the complexity is O(n^2) since there n*n grids.

Upvotes: 0

Sonic
Sonic

Reputation: 186

This can be solved by recognising that the number of paths to a particular node is just the sum of the number of paths to the node to the left + the number of paths to the node above. You just need to come up with an algorithm to process nodes in the correct order i.e. only process a node after its "parents" have been processed. I believe this can be O(n).

Upvotes: 1

Related Questions