面试题 08.12. 八皇后

堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

输入使用数组[wi, di, hi]表示每个箱子。

示例1:

输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
输出：6

示例2:

输入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
输出：10

提示:

• 箱子的数目不大于3000个。

Python 解法：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        matrix = [['.' for i in range(n)] for j in range(n)]
        res = []
        def backtrace(r):
            if r == n:
                res.append([''.join(matrix[i]) for i in range(n)])
                return
            for c in range(n):
                if check(r, c):
                    matrix[r][c] = 'Q'
                    backtrace(r+1)
                    matrix[r][c] = '.'
        def check(r, c):
            for i in range(n):
                if matrix[r][i] == 'Q' or  matrix[i][c] == 'Q':
                    return False
            tr, tc = r, c 
            tr, tc = tr-min(tr,tc), tc-min(tr, tc)
            while tr < n and tc < n:
                if matrix[tr][tc] == 'Q':
                    return False
                tr += 1
                tc += 1
            tr, tc = r, c 
            if tr + tc >= n-1:
                tr, tc = n-1, tr+tc-n+1
            else:
                tr, tc = tr+tc, 0
            while tr >= 0 and tc < n:
                if matrix[tr][tc] == 'Q':
                    return False
                tr -= 1
                tc += 1
            # while tr >= 0 and tc < n:
            #     if matrix[tr][tc] == 'Q':
            #         return False
            #     tr -= 1
            #     tc += 1
            # tr, tc = r, c
            # while  tr < n and tc >= 0:
            #     if matrix[tr][tc] == 'Q':
            #         return False
            #     tr += 1
            #     tc -= 1
            # tr, tc = r, c
            # while tr >= 0 and tc >= 0:
            #     if matrix[tr][tc] == 'Q':
            #         return False
            #     tr -= 1
            #     tc -= 1
            # tr, tc = r, c 
            # while tr < n and tc < n:
            #     if matrix[tr][tc] == 'Q':
            #         return False
            #     tr += 1
            #     tc += 1
            return True
        backtrace(0)
        return res