1
# Runtime: 197 ms (Top 21.3%) | Memory: 16.48 MB (Top 34.6%)
2

3

4
class Solution:
5
    def tilingRectangle(self, n: int, m: int) -> int:
6
        # try brute force backtracking?
7
        board = [[0 for _ in range(n)] for _ in range(m)]
8

9
        ans = math.inf
10

11
        def bt(counts):
12
            nonlocal ans
13
            if counts >= ans:
14
                return
15

16
            pos = None
17
            found = False
18
            for row in range(m):
19
                for col in range(n):
20
                    if board[row][col] == 0:
21
                        pos = (row, col)
22
                        found = True
23
                        break
24
                if found:
25
                    break
26
            if not found:
27
                ans = min(ans, counts)
28
                return
29

30
            # see how many difference size of squares we can place from this spot
31
            r, c = pos
32
            offset = 0
33
            while (
34
                r + offset < m
35
                and c + offset < n
36
                and board[r + offset][c] == 0
37
                and board[r][c + offset] == 0
38
            ):
39
                offset += 1
40
            # max can place size is offset
41
            for row in range(r, r + offset):
42
                for col in range(c, c + offset):
43
                    board[row][col] = 1
44
            # do bt and shrink
45
            while offset > 0:
46
                bt(counts + 1)
47
                # shrink
48
                for row in range(r, r + offset):
49
                    board[row][c + offset - 1] = 0
50
                for col in range(c, c + offset):
51
                    board[r + offset - 1][col] = 0
52
                offset -= 1
53

54
        bt(0)
55
        return ans