回溯法,当遍历到最后一行,此时的组合就可以被记录了。而如果不到的话,还需要为当前的行的queen选择合适的列。注意设置对脚线数组记录选定当前行当前列后,向左上的对角线和向右上的对角线,判断是否合法。其位置的计算是当前行数+选定列数,和总行数N-当前行数+选定列数。
class Solution: def solveNQueens(self, n: int) -> List[List[str]]: col = [False]*n udg = [False]*(2*n) dg = [False]*(2*n) res = [] grid = [['.' for _ in range(n)] for _ in range(n)] def dfs(currow): if currow == n: tempres = [] for i in range(n): line = '' for j in range(n): line += grid[i][j] tempres.append(line) res.append(tempres) return else: for i in range(n): if not col[i] and not udg[currow + i] and not dg[n - currow + i]: col[i] = udg[currow + i] = dg[n - currow + i] = True grid[currow][i] = 'Q' dfs(currow + 1) grid[currow][i] = '.' col[i] = udg[currow + i] = dg[n - currow + i] = False dfs(0) return res
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)