LeetCode-Go/51.go at master · HugoWen/LeetCode-Go · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package main

import "strings"

func solveNQueens(n int) [][]string {
    col := map[int]bool{}
    pie := map[int]bool{}
    na := map[int]bool{}
    queens := make(map[int]int, n)
    for i := 0; i < n; i++ {
        queens[i] = -1
    }
    ret := []map[int]int{}

    var dfs func(int)
    dfs = func(i int) {
        if i >= n {
            tmp := make(map[int]int, n)
            for k, v := range queens {
                tmp[k] = v
            }
            ret = append(ret, tmp)
            return
        }

        for j := 0; j < n; j ++ {
            if col[j] {
                continue
            }
            if pie[i + j] {
                continue
            }
            if na[i - j] {
                continue
            }

            col[j] = true;
            pie[i + j] = true;
            na[i - j] = true;
            queens[i] = j
            dfs(i + 1)
            queens[i] = -1
            delete(col, j)
            delete(pie, i + j)
            delete(na, i - j)
        }
    }

    dfs(0)
    res := make([][]string, len(ret))
    for k := 0; k < len(ret); k ++ {
        res[k] = []string{}
        for r := 0; r < len(ret[k]); r ++ {
            s := ""
            if ret[k][r] == 0 {
                s = "Q" + strings.Repeat(".", n - 1)
            } else {
                s += strings.Repeat(".", ret[k][r]) + "Q" + strings.Repeat(".", n - ret[k][r] - 1)
            }
            res[k] = append(res[k], s)
        }
    }
    return res
}