danielfranca - 7 months ago 79

Python 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:

- 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] - F(S) = 1 # There's only one way to reach the starting point
- For each cell i,j I check if it's blocked, if so F(i,j) = 0
- 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`

`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

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()
```

Source (Stackoverflow)