Grid Paths with Walls

A robot starts in the top-left square of a grid and wants to reach the bottom-right square. It moves one square at a time, only right or down, and it cannot enter a wall. grid is a list of rows in which 0 is an open square and 1 is a wall.

Write count_paths(grid) that returns the number of different routes the robot can take. If the starting or the finishing square is a wall, there are no routes.

Examples

count_paths([[0, 0, 0],
             [0, 0, 0]])     # returns 3
count_paths([[0, 0, 0, 0],
             [0, 1, 0, 0],
             [0, 0, 0, 1],
             [1, 0, 0, 0]])  # returns 3
count_paths([[0, 1],
             [1, 0]])        # returns 0

In the 2 by 3 grid with no walls the routes are right-right-down, right-down-right and down-right-right.

Constraints

• The grid has 1 to 100 rows, all of the same length (1 to 100)
• Every square is 0 or 1
• The answer can be very large; Python integers handle that