52. N-Queens II Leetcode Python

浏览数：29 / 时间：2015年06月08日

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

技术分享

这题的解法是建一个board表示行比如n=4 时候board=[1,3,0,2] 表示 0Q00,000Q,Q000,00Q0

利用对于dfs每次确认当前Board是否满足条件时候已经表示之前的格子都已经满足条件了。

在check 函数表示 queen 是否可以放在第k（depth）行j(row)列

class Solution:
    # @return an integer
    def __init__(self):
        self.count=0
    def check(self,k,j,board):
        for i in range(k):
            if board[i]==j or abs(k-i)==abs(board[i]-j):
                return False
        return True
    def dfs(self,depth,board,n):
        if depth==n:
            self.count+=1
        for row in range(n):
            if self.check(depth,row,board):
                s='.'*n
                board[depth]=row
                self.dfs(depth+1,board,n)
    def totalNQueens(self, n):
        board=[-1 for i in range(n)]
        self.dfs(0,board,n)
        return self.count

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

52. N-Queens II Leetcode Python