Count the number of paths from start to end with obstacles

Question

I'm trying to implement an algorithm that should count the number of paths from the bottom left to the top right of a matrix NxM. I ran it on some website which I upload the code and it runs a bunch of test cases, I can't see which test cases it's running against to so all I know is that it's failing in some of the test cases.

The complete description of the problem:

You are given a grid of cells with size N rows by M columns. A robot is situated at the bottom-left cell (row N-1, column 0). It can move from cell to cell but only to the right and to the top. Some cells are empty and the robot can pass through them but others are not and the robot cannot enter such cells. The robot cannot go outside the grid boundaries.

The robot has a goal to reach top-right cell (row 0, column M-1). Both the start and end cells are always empty. You need to compute the number of different paths that the robot can take from start to end. Only count paths that visit empty cells and move only to the right and up.

For that what I'm doing is:

1. Creating an empty grid NxM, which will be used to store the number of paths from starting point S to grid[i][j] for each grid[i][j]

2. F(S) = 1 # There's only one way to reach the starting point

3. For each cell i,j I check if it's blocked, if so F(i,j) = 0

4. For the remaining cells I sum the 2 possible ways: F(i-1,j) + F(i, j+1)

The Python code:

def count_the_paths(grid):
    N = len(grid)
    M = len(grid[0])

    ways = [[None for _ in range(M)] for _ in range(N)] # Generate empty matrix to store the number of ways
    ways[N-1][0] = 1 # There's only 1 way to reach the starting point

    for row in range(N-1, -1, -1):
        for col in range(0, M):
            if grid[row][col] == 1: # Blocked cell
                ways[row][col] = 0
            elif row != N-1 or col != 0: # If it's not the starting point
                ways[row][col] = 0
                if row < N-1:
                    ways[row][col] += ways[row+1][col]
                if col > 0:
                    ways[row][col] += ways[row][col-1]

    return ways[0][M-1]

For example, if the grid is:

grid = [
    [0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0],
]

The ways matrix is:

ways = [
    [1, 0, 0, 1, 4], 
    [1, 1, 0, 1, 3], 
    [1, 0, 0, 1, 2], 
    [1, 0, 1, 1, 1], 
    [1, 1, 1, 0, 0]
]

So the number of paths is 4, which is correct as far as I understood.

Does anyone has any idea about what I'm missing or doing wrong?

UPDATE: As @Tempux noted I've to store the MODULO 1000003 of the number of paths.

So I changed my code:

def count_the_paths(grid):
    N = len(grid)
    M = len(grid[0])

    ways = [[None for _ in range(M)] for _ in range(N)] # Generate empty matrix to store the number of ways
    ways[N-1][0] = 1 # There's only 1 way to reach the starting point

    for row in range(N-1, -1, -1):
        for col in range(0, M):
            if grid[row][col] == 1: # Blocked cell
                ways[row][col] = 0
            elif row != N-1 or col != 0: # If it's not the starting point
                ways[row][col] = 0
                if row < N-1:
                    ways[row][col] += ways[row+1][col] % 1000003
                if col > 0:
                    ways[row][col] += ways[row][col-1] % 1000003

    return ways[0][M-1]

But the error saying I produced incorrect answer is still there.

UPDATE 2:

As suggested by User_Targaryen I changed the line

if grid[row][col] == 1: # Blocked cell

to:

if grid[row][col] == "1": # Blocked cell

But it's still failing

UPDATE 3:

Then my last attempt, (tried with both char and integer) with the correction of the modular addition as suggested by Tempux:

def count_the_paths(grid):
    N = len(grid)
    M = len(grid[0])

    ways = [[None for _ in range(M)] for _ in range(N)] # Generate empty matrix to store the number of ways


    ways[N-1][0] = 1 # There's only 1 way to reach the starting point



    for row in range(N-1, -1, -1):
        for col in range(0, M):
            if grid[row][col] == 1: # Blocked cell - also tried with char instead


                ways[row][col] = 0
            elif row != N-1 or col != 0: # If it's not the starting point


                ways[row][col] = 0
                if row < N-1:
                    ways[row][col] += ways[row+1][col]
                    ways[row][col] %= 1000003                    
                if col > 0:
                    ways[row][col] += ways[row][col-1]
                    ways[row][col] %= 1000003                    

    return ways[0][M-1]

Still failing

FINAL UPDATE [SOLVED] User_Targaryen was right, there was an issue with their test cases (and they were chars, not integers) I got this response back:

Hi Daniel,

Thanks a lot for writing to us about this. There was an issue with some of the test cases of the problem. It is now fixed. In addition to that, in your solution you should change the way you check if a cell is occupied or not. Note that the input grid consists of strings of 0 and 1. They are not numbers.

We've increased your allowed number of attempts, so that you can submit more.

Thanks again

Thanks for everyone who helped me.

Answer 1

The number of paths grows exponentially, that is why in the problem statements says:

Write a method, which accepts N, M and the grid as arguments and returns one integer - the total number of different paths that the robot can take from the start to the end cell, MODULO 1,000,003.

so you should save number_of_paths % 1000003. That is why you are getting wrong answer.

---

I am not sure whether this will fix all the problems in your submission or not but

ways[row][col] += ways[row+1][col] % 1000003

is not the correct way of calculating modular addition. Instead you should do the following:

ways[row][col] += ways[row+1][col]
ways[row][col] %= 1000003

Answer 2

Looking at the problem statement and due to lack of information about the errors in the solution, I think that the input will be somewhat like:

grid = ['01100','00010','01010','01000','00010']

Because it says: The input grid will contain N strings with M characters each - either 0 or 1

Changing the following line in your code yielded 10 more points:

if grid[row][col] == '1': # Blocked cell

Edit: You can find a very similar question here. Submit your solution to check if your basic logic is correct.

Here is my accepted solution to the CodeChef problem:

def numWays(m,n,p):
  grid = [[0 for _ in range(n)] for _ in range(m)]
  ways = [[0 for _ in range(n)] for _ in range(m)]
  mod = 1000000007
  i = 0
  while i<p:
    i=i+1
    x,y = map(int, raw_input().split())
    grid[x-1][y-1]=1

  if grid[0][0]==1 or grid[m-1][n-1]==1:
    return 0

  ways[0][0]=1

  i=0
  ways[0][0] = 1
  while i<m:
    j = 0
    while j<n:
      if grid[i][j]==0:
        if i-1>=0 and j-1>=0:
          ways[i][j] = (ways[i][j-1] + ways[i-1][j]) % mod
        elif i-1>=0:
          ways[i][j] = ways[i-1][j]
        elif j-1>=0:
          ways[i][j] = ways[i][j-1]
      j=j+1
    i = i+1

  return ways[m-1][n-1]

def main():
  m,n,p = map(int, raw_input().split())
  print numWays(m,n,p)

main()