We'll use the grid below for walking through the solution:

Recursive Definition

If you've already solved the "Chaos in the Grid" problem, the recursive definition will be easier, so let's start with that.

From where can Chaos arrive at the bottom-right corner?

Just like in the previous problem, it can only arrive from the top and the left.

This means that the recursive definition is exactly the same:

Recursive Definition: The number of unique paths to get to the bottom-right square is the sum of the number of paths to get to the square immediately above it plus the number of distinct paths to get to the square immediately to its left.

Memoization

What can we use as a cache? Once again, since the problem involves the grid, similar to the previous problem, we can opt to use a Map with a string representing the square coordinates as the key, or we can use a nested array.

Base Case

Let's handle the base case now. If you remember, in the first problem, the base case was, if it's the first row, or the first column, return 1.

Can we do the same thing in this case? Let's take a look at a grid with only one row and a sleeping cat in the middle. In how many distinct ways can Chaos reach the bowl of treats?

Unfortunately, the answer is zero because he can't step on the cat.

The same would hold true if we only had one column.

Okay, so the base case can't be the first row and column filled with 1s; it must be the first square where Chaos is standing. Kind of...

What if the cat is sleeping on that square? In that case, Chaos can't even stand on that square.

So, we can say that the base case is if it's the first square (0, 0) and it doesn't have an obstacle, we can return 1. If there is an obstacle, we should return 0.

Is that enough?

In the previous problem, we populated the first row and column with 1s so there wasn't a chance of going out of bounds of the grid. However, in this case, that is not true. Let's use an example with only one row. In the recursive solution, Chaos is standing at the bottom-right square, and the recursive solution is the number of ways to get there from the top plus the number of ways from the left.

From the image, we can see that we'll get zero from the left side but, the "top" is out of bounds of the grid, so we need to account for that in the base case as well and return 0 in this scenario.

Now we have all the information we need and we can define the base case as:

Base Case: If the square contains a sleeping cat or is out of the bounds of the grid return 0, otherwise if the square is (0, 0) return 1.