当前位置：首页 > article >正文

【LeetCode】每日一题 2024_12_1 N 皇后（回溯，DFS）

article 2024/12/2 20:28:23

前言

每天和你一起刷 LeetCode 每日一题~

今日看点：回溯问题必学经典

LeetCode 启动！

题目：N 皇后

代码与解题思路

先读题：同一行同一列，两条对角线上只能同时存在一个皇后，题目要我们找出组成这样棋盘的所有可能性

假设我们遍历每一行每一列，每一行和每一列只放一个皇后，这样我们只需要判断对角线上有没有皇后存在即可，通过回溯遍历所有情况，将合法的情况记录并存入 ans 即可

核心问题：怎么判断对角线上是否存在其他的皇后？

1、对角线：左上到右下， 11， 22，33，行列相减的值是相同的，我们通过 d1 数组记录行列相减的值，这样就能判断当前位置对角线上是否存在皇后了

（注意：如果是 12， 23， 34，这种情况，行列相减是负数，我们可以通过让相减 + n 的做法规避出现负数的情况。）

2、对角线：右上到左下，13， 22， 31，行列相加的值是相同的，我们通过 d2 数组记录行列相加的值，这样就能判断当前位置对角线上是否存在皇后了

代码如下：

func solveNQueens(n int) (ans [][]string) {
    // 经典回溯 N 皇后问题
    col, st := make([]int, n), make([]bool, n)
    d1, d2 := make([]bool, n*2), make([]bool, n*2) // 用来放对角线对应的位置
    var dfs func(int)
    dfs = func(r int) { // 枚举行
        if r == n { // 皇后已经放置完成，将这种情况的棋盘构造并加入 ans 数组
            board := make([]string, n)
            for i, c := range col {
                board[i] = strings.Repeat(".", c)+"Q"+strings.Repeat(".", n-c-1)
            }
            ans = append(ans, board)
        }
        for c, v := range st { // 枚举列
            rc1, rc2 := r-c+n, r+c
            if !v && !d1[rc1] && !d2[rc2] { // 当前位置 && 俩对角线上没有放皇后
                col[r] = c // 在 r 行 c 列上放置皇后
                st[c], d1[rc1], d2[rc2] = true, true, true
                dfs(r + 1)
                st[c], d1[rc1], d2[rc2] = false, false, false // 恢复现场
            }
        }
    }
    dfs(0)
    return ans
}