# Find number of ways to traverse matrix of 0's and 1's

I solved a Daily Coding Challenge, but i suspect my code could be optimised. The challenge is the following:

You are given an N by M matrix of 0s and 1s. Starting from the top left corner, how many ways are there to reach the bottom right corner?
You can only move right and down. 0 represents an empty space while 1 represents a wall you cannot walk through. For example, given the following matrix:

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


Return two, as there are only two ways to get to the bottom right:
Right, down, down, right
Down, right, down, right
The top left corner and bottom right corner will always be 0.

You can see my solution below. Any tips on how to improve on it are very welcome.

def solution(matrix, x=0, y=0):
count = 0
right, left = False, False

if y == len(matrix) - 1 and x == len(matrix) - 1:  # found a way
return 1

if x < len(matrix) - 1:
if matrix[y][x+1] == 0:
count += solution(matrix, x+1, y)  # look right
right = True

if y < len(matrix) - 1:
if matrix[y+1][x] == 0:
count += solution(matrix, x, y+1)  # look down
left = True

if not right and not left:  # dead end
return 0

return count

if __name__ == "__main__":
print(solution([[0, 0, 0], [0, 0, 0], [0, 1, 0]]))


You don't need right and left: they add nothing that isn't already covered by count.

Compute lengths once rather than repeatedly.

Check for empty matrix rows and/or columns, or invalid x and y, if your code needs to handle such edge cases.

def solution(matrix, x=0, y=0):
count = 0
y_limit = len(matrix) - 1
x_limit = len(matrix) - 1

# Success.
if y == y_limit and x == x_limit:
return 1

# Look right.
if x < x_limit and matrix[y][x + 1] == 0:
count += solution(matrix, x + 1, y)

# Look down.
if y < y_limit and matrix[y + 1][x] == 0:
count += solution(matrix, x, y + 1)

return count

• I don't think edge cases have to be considered in my case. this helped, thank you! Jul 9 at 9:17