[LeetCode每日一题]51. N 皇后

ygxdsh

经典dfs例题，直接抄acwing的思路

class Solution {
public:
    int nn;
    vector<vector<string>> ans;
    vector<string> anss;
    bool y[10]={0},t[20]={0},k[20]={0};
    void dfs(int x)
    {
        if(x==nn) 
        {
            ans.push_back(anss);
            return;
        }
        for(int i=0;i<nn;i++)
        {
            if(!y[i]&&!k[x+i]&&!t[nn-x+i])
            {
                y[i]=k[x+i]=t[nn-x+i]=1;
                string s(nn,'.');
                s[i]='Q';
                anss[x]=s;
                dfs(x+1);
                y[i]=k[x+i]=t[nn-x+i]=0;
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        nn=n;
        anss.resize(n);
        dfs(0);
        return ans;
    }
};

Mr-Hate

可以说是回溯的模板题吧

class Solution {
public:
    vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n) {
        vector<bool> visr(n,false);vector<bool> visc(n,false);vector<bool> vism(2*n-1,false);vector<bool> visco(2*n-1,false);vector<string> ans(n,string(n,'.'));
        auto check_ans=[&](int& i,int& j)->bool{
        if(visr[i]||visc[j]||vism[i-j+n-1]||visco[i+j])
        return false;
        return true;
        };
        auto dfs=[&](auto&& dfs,int row){
        if(row==n){
            res.push_back(ans);
            return;
        }
        for(int i=0;i<n;i++){
            if(check_ans(row,i)){
                ans[row][i]='Q';
                visr[row]=visc[i]=vism[row-i+n-1]=visco[row+i]=true;
                dfs(dfs,row+1);
                ans[row][i]='.';
                visr[row]=visc[i]=vism[row-i+n-1]=visco[row+i]=false;
            }
            
        }
        return;
        };

        dfs(dfs,0);
        return res;
    }
};