51,N皇后

python

from typing import List
# 这道题还是比较经典的深搜递归调用的问题。
# 只需要保证二维列表的每一行,每一列,每一对角线只有一个皇后就好了。
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
# 定义三个集合,用来保证每一行,每一列,每一对角线只有一个皇后
self.col,self.pie,self.na = set(),set(),set()
# 定义一个列表用来存放最后的结果
self.res = []
self.dfs(n,0,[])
return self.res
# 递归函数,n代表行的总数,row代表行,cur用来存放找到每一行的皇后位置。
def dfs(self,n,row,cur):
# 遍历n行后,就找出所有皇后的位置了。
if row == n:
# 注意这里不能写成res.append(cur)
self.res.append(cur[:])
# 这一步最重要,判断条件,用来保证每一行每一列,对角线只有一个皇后
for index in range(n):
if index in self.col or (index + row) in self.pie or (index - row) in self.na:
continue
# 找出每一行皇后的位置。
str1 = ""
for i in range(n):
if i == index :
str1 += "Q"
else:
str1 += "."
# 找到皇后位置后,需要将这一行添加到对应的集合中
cur.append(str1)
self.pie.add(index + row)
self.na.add(index - row)
self.col.add(index)
self.dfs(n,row + 1,cur)
# 注意,遍历完之后,要将之前添加到集合中的数删除。
self.pie.remove(index + row)
self.na.remove(index - row)
self.col.remove(index)
cur.remove(str1)

A = Solution()
print(A.solveNQueens(4))

以上是 51,N皇后 的全部内容, 来源链接: utcz.com/z/531077.html

回到顶部