即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

LeetCode 51. N-Queens

编程语言 helloiamclh 94℃ 0评论
本文目录
[隐藏]

1.题意

求出含有n个皇后的所有的棋盘摆放方案

2.思路

经典的DFS + 回溯问题,使用loc[i]表示第i列的皇后在第几行,后面的就是DFS+了,各大算法和数据结构的书中都有这种问题,就不再写思路了.

3.代码

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<int>loc;
        for(int i = 0; i < n; i++){
            loc.push_back(-1);
        }
        vector<vector<string> >ans;
        DFS(loc, 0, n, ans);
        return ans;
    }
private:
    void DFS(vector<int>& loc, int id, int n, vector<vector<string> >& ans){
        if(id == n){
            vector<string>temp;
            for(int i = 0; i < n; i++){
                string s = "";
                for(int j = 0; j < n; j++){
                    if(j == loc[i]){
                        s += "Q";
                    } else{
                        s += ".";
                    }
                }
                temp.push_back(s);
            }
            ans.push_back(temp);
            return ;
        }
        for(int i = 0; i < n; i++){
            int flag = 0;
            for(int j = 0; j < id; j++){
                if((loc[j] == i) || (id + i == loc[j] + j) || (i - loc[j] == id - j)){
                    flag = 1;
                    break;
                }
            }
            if(flag) continue;
            loc[id] = i;
            DFS(loc, id + 1, n, ans);
            loc[id] = -1;
        }
    }
};

转载请注明:CodingBlog » LeetCode 51. N-Queens

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情