[LeetCode每日一题]52. N 皇后 II

ygxdsh

比昨天还简单，就对于每行，每斜着的一行分别设一个bool数组，再dfs就解决了

class Solution {
public:
    int nn,ans;
    bool y[10],k[20],t[20];
    void dfs(int x)
    {
        if(x==nn) 
        {
            ans++;
            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;
                dfs(x+1);
                y[i]=k[x+i]=t[nn-x+i]=0;
            }
        }
    }
    int totalNQueens(int n) {
        nn=n;
        dfs(0);
        return ans;
    }
};

Mr-Hate

昨天的代码简单改改就直接用了

class Solution {
public:

    int totalNQueens(int n) {
        int res=0;
        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;
            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;
    }
};