leetcode-yyc/52.n皇后-ii.py at main · yan-yuchen/leetcode-yyc · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#
# @lc app=leetcode.cn id=52 lang=python3
#
# [52] N皇后 II
#

# @lc code=start
class Solution:
    def totalNQueens(self, n: int) -> int:
        res = 0
        col = [False]*n
        dg = [False]*2*n
        udg = [False]*2*n
        path = [['.']*n for _ in range(n)]

        def dfs(j):
            if j == n:
                nonlocal res  # 不加这个报错local variable 'res' referenced before assignment
                res = res+1

            for i in range(n):
                if not col[i] and not dg[i+j] and not udg[i-j+n]:
                    col[i] = dg[i+j] = udg[i-j+n] = True
                    path[i][j] = 'Q'
                    dfs(j+1)
                    col[i] = dg[i+j] = udg[i-j+n] = False
                    path[i][j] = '.'

        dfs(0)
        return res


# @lc code=end