leetcode 51. N皇后

目录

https://leetcode-cn.com/problems/n-queens/

定义三个标记数组：

1. col 表示每列是否被占用，布尔类型
2. ul2dr 左上到右下的斜线是否被占用，长度是 2 × n - 1，下标转换：i = x - y + n - 1，因为在这个斜线上，横纵坐标的差是固定的
3. ur2dl 右上到左下的斜线是否被占用，长度是 2 × n - 1，下标转换：i = x + y，因为在这个对角线上，横纵坐标的和是固定的

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        mp = [['.']*n for i in range(n)]
        col = [False] * n
        ul2dr = [0] * (n*2-1)
        ur2dl = [0] * (n*2-1)
        ans = []
        def dfs(i):
            if i == n:
                ans.append([''.join(x) for x in mp])
            for j in range(n):
                pos1 = i - j + n - 1
                pos2 = i + j
                if not col[j] and ul2dr[pos1] == 0 and ur2dl[pos2] == 0: # 本位置未被占用
                    col[j] = True
                    ul2dr[pos1] += 1
                    ur2dl[pos2] += 1
                    mp[i][j] = 'Q'
                    dfs(i+1)
                    mp[i][j] = '.'
                    col[j] = False
                    ul2dr[pos1] -= 1
                    ur2dl[pos2] -= 1
        dfs(0)
        return ans