leetcode 51N皇后

简介: leetcode 51N皇后

N皇后

56f3c2a6d4d14d32a49b53d643a00eec.png递归遍历

主要是去除同行和同列

class Solution {
public:
    vector<vector<string>> result;
    vector<int>path;
    //求绝对值
    int abs(int a)
    {
        if (a < 0) return -a;
        else return a;
    }
    void backtraking(int n ,vector<bool> &used ,int deep)
    { 
      //当深度大于n时返回
        if(deep > n) return;
        //当路径为最大深度,找到路径存入
        if(path.size() == n)
        {
          //将数字路径转换成字符串路径
            vector<string> path_s;
            for(int i=0;i<n;i++)
            {
                string tmp ;
                for(int k=0;k<n;k++) tmp +='.';//建立n个.
                for(int j=0;j<n;j++)  if(j==path[i]) tmp[j] = 'Q';//在应该放Q的位置放Q
                path_s.push_back(tmp);//转换好的字符串存入路径
            }
            //存入结果
            result.push_back(path_s);
            return;
        }
    //层次循环,找到每一行的点。
        for(int i=0 ; i<n; i++)
        {
            if(used[i] == true) continue; //该点用过了,跳过。一个树枝的点只能用一次
            pair<int,int> x(deep,i);//当前可能有效点
            bool flag = true;
            //当前点,和path路径里面所有点依次对比
            for(int j =0 ; j < path.size() ;j++)
            {
                pair<int,int> y(j,path[j]);//path之前加入的点
                //检测当前点与之前路径点,是否在一列一行和对角线
                if( abs(x.first - y.first)==0 ||  abs(x.second - y.second)==0 
                    || abs(x.first - y.first) == abs(x.second - y.second) ) 
                    flag = false;
            }
            //检测是合格点,加入path
            if(flag == true)
            {
              //记录该点使用
                used[i] = true;
                path.push_back(i);
                //递归,深度+1(找下一行)
                backtraking(n,used,deep+1);
                path.pop_back();
                used[i] = false;
            }
        }
        return;
    }
    vector<vector<string>> solveNQueens(int n) { 
        vector<bool> used(n,false);
        backtraking(n ,used,0);
        return result;
    }
};



相关文章
|
6月前
|
机器学习/深度学习 算法
leetcode51N皇后刷题打卡
leetcode51N皇后刷题打卡
48 0
代码随想录Day26 贪心01 LeetCode T53 最大子数组和
代码随想录Day26 贪心01 LeetCode T53 最大子数组和
42 0
|
测试技术
代码随想录Day24 LeetCode T491 递增子序列 LeetCode T46 全排列 LrrtCode T47 全排列II
代码随想录Day24 LeetCode T491 递增子序列 LeetCode T46 全排列 LrrtCode T47 全排列II
38 1
|
1月前
|
机器学习/深度学习 算法 C++
Leetcode第52题(N皇后II)
这篇文章介绍了解决LeetCode第52题(N皇后II)的C++代码实现,使用深度优先搜索(DFS)算法来找出所有可能的解决方案,并计算出不同的解决方案数量。
17 1
|
1月前
|
机器学习/深度学习 算法 C++
Leetcode第51题(N皇后)
这篇文章介绍了解决LeetCode第51题N皇后问题的C++深度优先搜索(DFS)算法实现,包括详细的代码和解题思路。
16 0
Leetcode第51题(N皇后)
|
机器学习/深度学习
【N皇后】
【N皇后】
|
6月前
代码随想录 Day40 动态规划08 LeetCodeT198打家劫舍 T213打家劫舍II T337 打家劫舍III
代码随想录 Day40 动态规划08 LeetCodeT198打家劫舍 T213打家劫舍II T337 打家劫舍III
49 0
|
6月前
|
机器学习/深度学习
leetcode-52:N皇后 II
leetcode-52:N皇后 II
27 0
|
机器学习/深度学习 算法 安全
LeetCode - #52 N皇后 II
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
LeetCode - #52 N皇后 II
|
机器学习/深度学习 算法 Java