LeetCode 51. N 皇后

LeetCode 51. N 皇后

思路：
dfs确定了搜索顺序就好做了
1、搜索顺序是每一行，然后枚举一行的每一列
2、搜索顺序是枚举每一个格子
代码1：

class Solution {
public:
    //初始化
    int n;
    vector<vector<string>> res;
    vector<bool> st,dg,udg;
    vector<string> path;

    vector<vector<string>> solveNQueens(int _n) {
        n=_n;
        path= vector<string>(n,string(n,'.'));
        st= vector<bool> (n);
        dg=udg=vector<bool> (2*n);

        dfs(0);
        return res;
    }

    void dfs(int u){
        if(u == n){
            res.push_back(path);
            return;
        }

        //对于每行 按照列来搜索
		//因为枚举的是每一行u 所以每一行不会出现两个皇后
        for(int i=0;i<n;i++){
            if(!st[i] && !udg[u-i+n] && !dg[i+u]){
                st[i]=udg[u-i+n]=dg[u+i]=true;
                path[u][i]='Q';
                dfs(u+1);
                st[i]=udg[u-i+n]=dg[i+u]=false;
                path[u][i]='.';
            }
        }

    }
};

代码2：

class Solution {
public:
    //初始化
    int n;
    vector<vector<string>> res;
    vector<bool> col,row,dg,udg;
    vector<string> path;

    vector<vector<string>> solveNQueens(int _n) {
        n=_n;
        path= vector<string>(n,string(n,'.'));
        row=col= vector<bool> (n);
        dg=udg=vector<bool> (2*n);

        dfs(0,0,0);

        return res;
    }
    //xy坐标 s皇后个数
    void dfs(int x,int y,int s){
        if(y == n) y=0,x++;
        if(x == n){
            //x到最后一行了 且 皇后的个数也到了n
            if(s == n){
                res.push_back(path);
            }
            return;
        }
        //两种搜索顺序 当前格子放皇后或者不放
        //不放
        dfs(x,y+1,s);

        //放皇后
        if(!col[x] &&!row[y] && !dg[x+y] && !udg[y-x+n]){
            col[x]=row[y]=dg[x+y]=udg[y-x+n]=true;
            path[x][y]='Q';
            dfs(x,y+1,s+1);
            col[x]=row[y]=dg[x+y]=udg[y-x+n]=false;
            path[x][y]='.';
        }

    }
};