标签：False idx self return range path Queens

51. N-Queens 

https://leetcode.cn/problems/n-queens/ 

class Solution:
    def is_valid(self, path, x, y):
        """ 给出现有的棋盘path，和位置（x,y）,判断在（x，y）处放置棋子是否会有冲突 """
        for i in range(x):
            if path[i][y] == "Q":  
                return False
        for j in range(y):
            if path[x][j] == "Q":
                return False
            
        # i == j
        i, j = x - 1, y - 1
        while i >= 0 and j >= 0:
            if path[i][j] == "Q":
                return False
            i -= 1
            j -= 1
        
        # i + j = k
        i, j = x - 1, y + 1
        while i >= 0 and j < self.n:
            if path[i][j] == "Q":
                return False
            i -= 1
            j += 1
        
        return True

    def dfs(self, path, idx):
        """ 尝试在第idx行放置皇后 """
        if idx == self.n:
            tmp = list( map(lambda x: "".join(x), path) )  # 将当前棋盘path的每一行字符数组，拼接成字符串
            self.res.append(tmp)
            return
        
        for j in range(self.n):
            if self.is_valid(path, idx, j) == False:
                continue
            path[idx][j] = "Q"
            self.dfs(path, idx+1)
            # 恢复现场 restore
            path[idx][j] = "."

    def solveNQueens(self, n: int) -> List[List[str]]:
        self.n = n
        path = [ ["."]*n for _ in range(n)]
        self.res = []
        idx = 0
        self.dfs(path, idx)
        return self.res 
        

View Code

 

 

52. N皇后 II

https://leetcode.cn/problems/n-queens-ii/

class Solution:
    def is_valid(self, path, x, y):
        for i in range(x):
            if path[i][y] == "Q":
                return False
        for j in range(y):
            if path[x][j] == "Q":
                return False
        i, j = x-1, y-1
        while i >= 0 and j >= 0:
            if path[i][j] == "Q":
                return False 
            i -= 1
            j -= 1

        i, j = x - 1, y + 1
        while i >= 0 and j < self.n:
            if path[i][j] == "Q":
                return False
            i -= 1
            j += 1
        
        return True
    
    def dfs(self, path, idx):
        if idx == self.n:
            self.cnt += 1
            return 
        
        for j in range(self.n):
            if self.is_valid(path, idx, j) == False:
                continue 
            path[idx][j] = "Q"
            self.dfs(path, idx+1)
            path[idx][j] = "."
        
    def totalNQueens(self, n: int) -> int:
        self.n = n
        self.cnt = 0
        path = [["."]*n for _ in range(n)]
        self.dfs(path, 0)
        return self.cnt

View Code

 

标签：False,idx,self,return,range,path,Queens
From： https://www.cnblogs.com/zijidan/p/16882528.html