Number of Ways of Cutting a Pizza LeetCode solution in Python

1
class Solution:
2
    def ways(self, p: List[str], k: int) -> int:
3
        m, n = len(p), len(p[0])
4
        apples = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
5
        # number of apples in (0,0) to (i,j)
6
        apples[1][1] = 0 if p[0][0] == "." else 1
7
        for j in range(1, n):
8
            apples[1][j + 1] = apples[1][j] if p[0][j] == "." else apples[1][j] + 1
9
        for i in range(1, m):
10
            cur_apple = 0 if p[i][0] == "." else 1
11
            apples[i + 1][1] = apples[i][1] + cur_apple
12
            for j in range(1, n):
13
                if p[i][j] == "A":
14
                    cur_apple += 1
15
                apples[i + 1][j + 1] = apples[i][j + 1] + cur_apple
16

17
        def getApples(x, y, z, w):
18
            # get the number of apples within range
19
            # x,y: top-left coordinates of current pizza
20
            # z,w: bottom-right
21
            return (
22
                apples[z + 1][w + 1]
23
                + apples[x][y]
24
                - apples[z + 1][y]
25
                - apples[x][w + 1]
26
            )
27

28
        @lru_cache(None)
29
        def cut(c, x, y, z, w):
30
            # c: number of cuts already cut
31
            # x,y: top-left coordinates of current pizza
32
            # z,w: bottom-right
33
            if c == k - 1:
34
                return 1 if getApples(x, y, z, w) > 0 else 0
35

36
            r = 0
37
            # horizontal cuts
38
            i = x
39
            while i < z:
40
                if getApples(x, y, i, w) > 0:
41
                    break
42
                i += 1
43
            while i < z:
44
                r += cut(c + 1, i + 1, y, z, w)
45
                i += 1
46
            # vertical cuts
47
            j = y
48
            while j < w:
49
                if getApples(x, y, z, j) > 0:
50
                    break
51
                j += 1
52
            while j < w:
53
                r += cut(c + 1, x, j + 1, z, w)
54
                j += 1
55

56
            return r
57

58
        return cut(0, 0, 0, m - 1, n - 1) % (10**9 + 7)