user3182811 -4 years ago 199

C++ Question

*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.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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.

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

Latest added