网站备案一般多久,懂装修公司怎么样,网站开发用php还pyt h on,区块链开发违法吗执行结果#xff1a;通过 题目#xff1a;51 N皇后
按照国际象棋的规则#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上#xff0c;并且使皇后彼此之间不能相互攻击。
给你一个整数 n #…执行结果通过 题目51 N皇后
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。 示例 1 输入n 4
输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]
解释如上图所示4 皇后问题存在两个不同的解法。示例 2
输入n 1
输出[[Q]]提示
1 n 9
代码以及解题思路
代码
class Solution:def solveNQueens(self, n: int) - List[List[str]]:ans []def dfs(i, a):if i n: ans.append([. * j Q . * (n - j - 1) for j in a])returnfor j in range(n):if all(j1 ! j and j1 - i1 ! j - i and j1 i1 ! j i for i1, j1 in enumerate(a)):dfs(i 1, a [j])for i in range(n): dfs(1, [i])return ans解题思路
初始化结果列表 ans []用来存储所有满足条件的N皇后摆放方式。定义深度优先搜索函数 dfs(i, a) i当前正在尝试放置皇后的行数从1开始。a一个列表存储了到目前为止每一行皇后放置的列索引从0开始。递归终止条件 if i n:当i等于n时说明已经成功地在每一行都放置了一个皇后此时将当前摆放方式添加到结果列表中。ans.append([. * j Q . * (n - j - 1) for j in a])将当前摆放方式转换为字符串列表每个字符串代表棋盘的一行Q表示皇后.表示空位。递归过程 遍历当前行的每一列j从0到n-1。检查当前列j是否安全即是否不与之前放置的皇后冲突。 all(j1 ! j and j1 - i1 ! j - i and j1 i1 ! j i for i1, j1 in enumerate(a))检查当前列j和之前每一行放置的皇后j1是否在同一列、同一主对角线或同一副对角线上。如果安全则递归调用dfs(i 1, a [j])将当前列j添加到已放置皇后的列索引列表中并尝试在下一行放置皇后。启动搜索 遍历第一行的每一列i从0到n-1作为搜索的起点调用dfs(1, [i])开始搜索。返回结果 返回所有满足条件的N皇后摆放方式ans。
总结
这段代码通过深度优先搜索DFS和回溯算法尝试在N×N的棋盘上放置N个皇后并记录所有满足条件的摆放方式。通过递归和条件判断确保每一行放置的皇后不与之前放置的皇后在同一列、同一主对角线或同一副对角线上。
