 user3182811 -4 years ago 199
C++ Question

# 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 ? justmscs

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

initialize `grid = 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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download