The Basic Problem

Given a grid of v vertical roads and h horizontal roads, find the number of ways to go from the top-left intersection to the bottom-right, moving only right or down.

For example, a grid of v = 4 and h = 3 would look like this:

+-+-+-+
| | | |
+-+-+-+
| | | |
+-+-+-+

Then the answer is 10. Easy enough, right? I suspect some of you are already typing in factorial stuff...

The Twist

But wait! Due to some obscure reason, some of the intersections are blocked, so you can't pass through them. In other words, you cannot use all four road segments connected to such intersection.

Now, a grid with one blocked intersection might look like this:

+-+-+-+    +-+-+-+
| | | |    |   | |
+-X-+-+    +   +-+
| | | |    |   | |
+-+-+-+ or +-+-+-+

Then the answer is 4.

Task

The function lattice_paths should accept one input, which will be a two-dimensional list, and return the number of ways to travel from top-left to bottom-right.

Each value in the input list will indicate whether the corresponding intersection is available or not. For example, the two grids discussed above will be passed as follows:

# The following should return 10
lattice_paths([
    [True, True, True, True],
    [True, True, True, True],
    [True, True, True, True]
])
# The following should return 4
lattice_paths([
    [True, True, True, True],
    [True, False, True, True],
    [True, True, True, True]
])

The top-left and bottom-right intersection will always be available, i.e. True. Also, it is guaranteed that v >= 2 and h >= 2, the array shape is rectangular, and all elements are boolean values.

Also, do not modify the input array!

Acknowledgement

This problem was inspired by Project Euler #15: Lattice Paths.