【leetcode】51 N-Queens

发表于 | 分类于 ，


描述

n 皇后问题

样例

样例1

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 4
输出:
   [
 	   [".Q..",  // Solution 1
 	    "...Q",
 	    "Q...",
 	    "..Q."],

 	   ["..Q.",  // Solution 2
 	    "Q...",
 	    "...Q",
 	    ".Q.."]
 	 ]

思路

回溯，注意一些小问题，下一次递归直接到下一行，而不是 pos + 1 这样会节省很多时间。
同样，本题可以创建一个数组只保存放皇后位置的列下标，更快一些。

代码

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Solution {
public:
    int size ;
    int count_kind;
    bool ok(const vector<string> & temp,int row ,int col){
        //valify the col, i means row
        for(int i=0;i<size;i++){
            if(i == row){ continue; }
            if(temp[i][col] == 'Q'){
                return false;
            }
        }

        //valify the x
        int dir[4][2]={
            {-1,-1},
            {-1,1},
            {1,-1},
            {1,1}
        };

        for(int i=0;i<4;i++){
            int row_temp = row;
            int col_temp = col;
            while(1){
                row_temp += dir[i][0];
                col_temp += dir[i][1];
                if(row_temp<0 || row_temp>=size || col_temp<0 || col_temp>= size){
                    break;
                }
                if(temp[row_temp][col_temp] == 'Q'){
                    return false;
                }
            }
        }
        return true;
    }

    // void backtrack(vector<vector<string>> & result, vector<string> & temp,int count,int pos){
    //     if(count == size ){
    //         result.push_back(temp);
    //         count_kind++;
    //         return;
    //     }

    //     for(int i=pos;i<size *size;i++){
    //         temp[i/size][i%size] = 'Q';
    //         int row = i/size;
    //         if(ok(temp,i)){
    //             backtrack(result,temp,count+1,i+1);
    //         }
    //         temp[i/size][i%size] = '.';
    //     }
    // }

    void backtrack(vector<vector<string>> & result, vector<string> & temp,int count,int current_row){
        if(count == size ){
            result.push_back(temp);
            count_kind++;
            return;
        }

        if(current_row >= size){return ;}

        for(int i=0;i<size;i++){
            temp[current_row][i] = 'Q';
            if(ok(temp,current_row,i) ){
                backtrack(result,temp,count+1,current_row+1);
            }
            temp[current_row][i] = '.';
        }
    }

public:
    vector<vector<string>> solveNQueens(int n) {
        size = n;
        count_kind = 0;
        vector<vector<string>> result;
        vector<string>  temp(n,string(n,'.'));
        backtrack(result,temp,0,0);

        return result;
    }
};

vector< vector<string> > solveNQueens(int n) {
    vector< vector<string> > result;
    vector<int> solution(n);

    solveNQueensRecursive(n, 0, solution, result);

    return result;
}

参考

原题链接