Leetcode 52. N-Queens II [Python]

只用统计总组合数,设置p数组,p[i]表示第i行的棋子放在哪个列上,check函数检查,当前行之前的行,是否有已经选择了该列,或者与该列成为对角线。
设置dfs,当走到第n行了,说明找到了一个组合,res += 1.如果不行,则遍历全部列,给当前的第k行,并check,如果可以,则此行找到了,记录到p数组中,并继续dfs找第k+1行该在哪一列。

class Solution: 
    def totalNQueens(self, n: int) -> int:
        p = [-1]*n
        self.res = 0
        
        def check(rowk, colj, p):
            for prev_row in range(rowk):
                if p[prev_row] == colj or abs(p[prev_row] - colj) == abs(prev_row - rowk):
                    return 0
            return 1
        
        def dfs(n, rowk):
            if rowk == n:
                self.res += 1
            else:
                for colj in range(n):
                    if check(rowk, colj, p):
                        p[rowk] = colj
                        dfs(n, rowk+1)
        
        dfs(n, 0)
        return self.res

2021,遇到了贵人,感谢唐老师,感谢岳老师。感恩上帝。希望2022年可以回到最想去的地方吧。。Amen

上一篇:n皇后递归,帮忙看一下哪里错了,谢谢


下一篇:AcWing 93. 递归实现组合型枚举题解