As usual, we need to define the base case, the recursive definition, and a way to memoize the repeated subproblems.

We'll use the grid below:

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.

Let's see the brute-force solution:

function chaosInTheGridWithCats(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  function helper(row, col) {
    if (row < 0 || col < 0 || grid[row][col] === "C") {
      return 0;
    }
    if (row === 0 && col === 0) {
      return 1;
    }

    return helper(row - 1, col) + helper(row, col - 1);
  }

  return helper(rows - 1, cols - 1);
}

Now with a Map as a cache:

function chaosInTheGridWithCats(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const cache = new Map();

  function helper(row, col) {
    if (row < 0 || col < 0 || grid[row][col] === "C") {
      return 0;
    }
    if (row === 0 && col === 0) {
      return 1;
    }

    const key = `${row} ${col}`;

    if (cache.has(key)) {
      return cache.get(key);
    }

    const paths = helper(row - 1, col) + helper(row, col - 1);

    cache.set(key, paths);

    return paths;
  }

  return helper(rows - 1, cols - 1);
}

Finally, the solution with a nested array as a cache:

function chaosInTheGridWithCats(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  const cache = new Array(rows).fill().map(() => new Array(cols).fill(0));

  function helper(row, col) {
    if (row < 0 || col < 0 || grid[row][col] === "C") {
      return 0;
    }
    if (row === 0 && col === 0) {
      return 1;
    }

    if (cache[row][col] !== 0) {
      return cache[row][col];
    }

    cache[row][col] = helper(row - 1, col) + helper(row, col - 1);

    return cache[row][col];
  }

  return helper(rows - 1, cols - 1);
}

// Test Cases:

const grid1 = [
  ["", "C"],
  ["", ""],
];
const grid2 = [["", "C"]];
const grid3 = [
  ["", "", ""],
  ["", "C", ""],
  ["", "", ""],
];
const grid4 = [
  ["", "", "", "", "C"],
  ["", "C", "", "", ""],
  ["", "", "", "C", ""],
];
const grid5 = [
  ["", "", "", "", "C", ""],
  ["", "C", "", "", "", ""],
  ["", "", "", "", "", ""],
  ["", "", "", "C", "", ""],
  ["", "C", "", "", "", ""],
  ["", "", "", "", "", ""],
];

console.log(chaosInTheGridWithCats(grid1) === 1);
console.log(chaosInTheGridWithCats(grid2) === 0);
console.log(chaosInTheGridWithCats(grid3) === 2);
console.log(chaosInTheGridWithCats(grid4) === 2);
console.log(chaosInTheGridWithCats(grid5) === 43);
// All test cases should log true

In the bottom-up approach, we are starting from the top-left corner of the grid.

We can't immediately fill it with 1, as the cat might be sleeping on it.

This means that:

1. If we find a square where the cat is sleeping, we should assign the value of that square to be 0.

2. If the square doesn't have a cat in it and it is the top-left square (0, 0), then fill the dp array for the square with 1.

3. Otherwise, the square's value will be the number of distinct paths from the top plus the number of distinct paths from the left. If the value is out of bounds of the grid, it is 0.

One final thing we haven't discussed is what data structure we would use for a dp object. Since we are dealing with a grid (nested array), a nested array seems appropriate as a dp object as well.

---

Let's go through an example grid step-by-step:

Step 1: Since the square (0, 0) doesn't have a sleeping cat in it, we fill the dp array for that square with 1.

Step 2: Next, we'll start iterating through the grid, row by row, and fill in each square by summing the values from the top and left. The first square to consider is (0, 1). The value from the top is 0 as it is out of bounds, and the value from the left is 1, so the value for (0, 1) is 1.

Step 3: In the last square of the first row, we have the same situation as in the previous step. The top is out of bounds, and the value to the left is 1, so the value for the square (0, 2) is 1.

Step 4: In the second row, first column, square (1, 0), the value to the left is out of bounds, thus 0, and the top value is 1, which equals 1.

Step 5: We have a sleeping cat at the next square, and we don't want to disturb it, so we'll leave the value as 0 for that square.

Step 6: Next, the value to the left is 0 as we have a sleeping cat there, and the value to the top is 1, so the sum is 1.

Step 7: In the seventh step, the value to the top is 1, and the value to the left is 0 as it is out of bounds, so the sum is 1.

Step 8: Here we have a sleeping cat at the top, so the value is 0, and 1 to the left, so once again the sum is 1.

Step 9: Finally, we reach the last square where the value from the top is 1 and from the left is 1, so the sum is 2, which is our final result.

Let's see the code implementation:

function chaosInTheGridWithCats(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  const dp = new Array(rows).fill().map(() => new Array(cols).fill(0));

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === "C") {
        dp[row][col] = 0;
      } else if (row === 0 && col === 0) {
        dp[row][col] = 1;
      } else {
        let fromTop = row > 0 ? dp[row - 1][col] : 0;
        let fromLeft = col > 0 ? dp[row][col - 1] : 0;
        dp[row][col] = fromTop + fromLeft;
      }
    }
  }

  return dp[rows - 1][cols - 1];
}

The time and space complexities in this problem are the same as in the previous one, "Chaos in the Grid".

The brute force recursive approach's time complexity without memoization is exponential, O(2^(R + C)), as we have to explore overlapping subproblems many times. R stands for the number of rows, and `C stands for the number of columns.

The space complexity for this approach is O(R + C). This is because the maximum depth of the recursion stack occurs when the recursion follows a path from the top-left to the bottom-right corner, which is R + C - 1 deep.

For the bottom-up approach and the top-down approach with memoization, the time and space complexities are identical. Every grid cell needs to be calculated once, and we are filling a cache object with the same number of values, so both the time and space complexities are O(R * C).