Number of Ways of Cutting a Pizza LeetCode solution in JavaScript

1
var ways = function (pizza, k) {
2
  const height = pizza.length;
3
  const width = pizza[0].length;
4
  const APPLE = "A";
5

6
  const cache = {};
7
  const dfs = (slices, startRow, startCol) => {
8
    // if we cut the entire pizza return 0
9
    if (startRow >= height || startCol >= width) return 0;
10

11
    // see if the parameters of the DFS has already been seen
12
    // if i has been seen, return the value
13
    const key = [slices, startRow, startCol].join("-");
14
    if (cache[key]) return cache[key];
15

16
    // if there is only 1 slice left to be made
17
    // find out if there is an apple in the slice
18
    if (slices === 1) {
19
      for (let row = startRow; row < height; row++) {
20
        for (let col = startCol; col < width; col++) {
21
          if (pizza[row][col] === APPLE) {
22
            return (cache[key] = 1);
23
          }
24
        }
25
      }
26
      return (cache[key] = 0);
27
    }
28

29
    // create a variable to total the number of ways
30
    let totalWays = 0;
31
    // create a variable to see if we have found an apple
32
    let hasApple = false;
33
    // decrement the number of slices left to be made
34
    slices--;
35

36
    // try to cut horizontally checking if we have found an apple
37
    // if we have found an apple keep cutting every row after that row
38
    for (let row = startRow; row < height; row++) {
39
      // to find an apple we search the current row if it has an apple in it
40
      // this will only run as long as we have not found an apple and in a current column
41
      for (let col = startCol; col < width && !hasApple; col++) {
42
        if (pizza[row][col] === APPLE) {
43
          hasApple = true;
44
        }
45
      }
46

47
      // if we have found an apple cut the pizza horizontally
48
      if (hasApple) {
49
        totalWays += dfs(slices, row + 1, startCol);
50
      }
51
    }
52

53
    // same as above except this time we cut vertically
54
    hasApple = false;
55
    for (let col = startCol; col < width; col++) {
56
      for (let row = startRow; row < height && !hasApple; row++) {
57
        if (pizza[row][col] === APPLE) {
58
          hasApple = true;
59
        }
60
      }
61
      if (hasApple) {
62
        totalWays += dfs(slices, startRow, col + 1);
63
      }
64
    }
65

66
    // return the number of ways
67
    return (cache[key] = totalWays % 1000000007);
68
  };
69
  return dfs(k, 0, 0);
70
};