【数据结构和算法】_10_剪枝

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【数据结构和算法】_10_剪枝，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含698字，纯文字阅读大概需要1分钟。

内容图文

【一】 Interview（面试题）

 

【1.1】 LeetCode 51 52：N Queens（N皇后问题）

题目说明：西洋象棋，如何将 n 个皇后放置在 n x n 的棋盘上，并且使得皇后之间不能相互攻击

• DFS（深度优先搜索）

result = []

# 深度优先遍历
def DFS(cols, na, pie, n):
    '''
    :param cols: 列表，存储皇后所在的列的索引
    :param na: 列表，存储皇后辐射的反斜区域
    :param pie: 列表，存储皇后辐射的正斜区域
    :param n: 数字，表示有几个皇后
    '''
    p = len(cols)
    if p == n:
        result.append(cols)
        return None
    for q in range(n):
        if q not in cols and p-q not in na and p+q not in pie:
            DFS(cols+[q], na+[p-q], pie+[p+q], n)

# 调用函数并返回结果
def solveNQueen(n):
    DFS([], [], [], n)
    return [ ['.'*i + 'Q' + '.'*(n-i-1) for i in sol] for sol in result ]

print(solveNQueen(4))

内容总结

以上是互联网集市为您收集整理的【数据结构和算法】_10_剪枝全部内容，希望文章能够帮你解决【数据结构和算法】_10_剪枝所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---