首页 > 其他 > 详细

51N皇后

时间:2020-07-13 20:33:47      阅读:51      评论:0      收藏:0      [点我收藏+]
from typing import List
# 八皇后问题,用递归的方法来写。
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
# 如果n < 1直接返回空列表
if n < 1:return []
# 定义变量用来存放最后的结果
self.res = []
# 定义几个集合,用来确保行和列,对角线只有一个皇后,
# 这里我们以行来遍历,因此只需要定义列,两个对角线
self.col,self.pie,self.na = set(),set(),set()
self.dfs(n,0,[])
return self.res
def dfs(self,n,row,cur):
# 递归完成,将结果放入self.res
if row == n:
# 注意这里的写法。
# 不能写成self.res.append(cur)
self.res.append(cur[:])
return
# 进行遍历列。
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 index1 in range(n):
if index1 == index :
str1 += "Q"
else :str1 += "."
# cur为临时列表
cur.append(str1)
# 已经添加过字符串了,因此将当前行,列对角线的值写入集合
self.col.add(index)
self.pie.add(index + row)
self.na.add(index - row)
# 然后进行递归下一行
self.dfs(n,row + 1,cur)
# 注意递归完成后一定要清除当前行列,对角线的数据。
cur.remove(str1)
self.col.remove(index)
self.pie.remove(index + row)
self.na.remove(index - row)

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

51N皇后

原文:https://www.cnblogs.com/cong12586/p/13295276.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!