LeetCode 51. N 皇后 --Golang
原题链接
简单
作者:
迷弟
,
2024-07-25 13:16:49
,
所有人可见
,
阅读 5
func solveNQueens(n int) [][]string {
// Initialize the board
g := make([][]byte, n)
for i := range g {
g[i] = make([]byte, n)
for j := range g[i] {
g[i][j] = '.'
}
}
col := make([]bool, n)
row := make([]bool, n*2)
diag := make([]bool, n*2)
var result [][]string
var dfs func(x int)
dfs = func(x int) {
if x == n {
solution := make([]string, n)
for i := range g {
solution[i] = string(g[i])
}
result = append(result, solution)
return
}
for y := 0; y < n; y++ {
if !col[y] && !row[x+y] && !diag[n+y-x] {
g[x][y] = 'Q'
col[y] = true
row[x+y] = true
diag[n+y-x] = true
dfs(x + 1)
g[x][y] = '.'
col[y] = false
row[x+y] = false
diag[n+y-x] = false
}
}
}
dfs(0)
return result
}