题解 | #N皇后问题#

N皇后问题

https://www.nowcoder.com/practice/c76408782512486d91eea181107293b6

class Solution {
public:
    /**
     *DFS深度优先搜索解决
     */
    const int N=20;
    int ans=0,size=0;
    bool col[20]={0},dg[20]={0},udg[20]={0};
    int Nqueen(int n) {
        size=n;
        dfs(0);
        return ans;
    }
    
    void dfs(int x){
        if(x==size){//满足答案,更新答案,并返回
            ans++;
            return;
        }
        for(int i=0;i<size;i++){//将棋盘按行读取
            if(!col[i]&&!dg[x+i]&&!udg[-x+i+size]){
                col[i]=dg[x+i]=udg[-x+i+size]=true;//更新状态
                dfs(x+1);//递归
                col[i]=dg[x+i]=udg[-x+i+size]=false;//恢复现场
            }
        }
    }
};

全部评论

相关推荐

投递长鑫存储等公司7个岗位
点赞 评论 收藏
分享
头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务