力扣算法题—051N皇后问题

- 日理万妓 2022-10-02 15:55 128阅读 0赞

1 #include "000库函数.h"
      2 
      3 
      4 //使用回溯法来计算
      5 //经典解法为回溯递归，一层一层的向下扫描，需要用到一个pos数组，
      6 //其中pos[i]表示第i行皇后的位置，初始化为 - 1，然后从第0开始递归，
      7 //每一行都一次遍历各列，判断如果在该位置放置皇后会不会有冲突，以此类推，
      8 //当到最后一行的皇后放好后，一种解法就生成了，将其存入结果res中，
      9 //然后再还会继续完成搜索所有的情况，代码如下：17ms
     10 class Solution {
     11 public:
     12     vector<vector<string>> solveNQueens(int n) {        
     13         vector<vector<string>>res;
     14         vector<int>pos(n, -1);
     15         NQueue(res, pos, 0);
     16         return res;
     17     }
     18     
     19     void NQueue(vector<vector<string>>&res, vector<int>&pos, int t) {
     20         int n = pos.size();
     21         if (t == n) {
        //组合成功
     22             vector<string>v(n, string(n, '.'));//这初始化绝逼了
     23             for (int i = 0; i < n; ++i)
     24                 v[i][pos[i]] = 'Q';
     25             res.push_back(v);
     26         }
     27         else
     28             for (int k = 0; k < n; ++k)
     29                 if (Danger(pos, t, k)) {
     30                     pos[t] = k;
     31                     NQueue(res, pos, t + 1);
     32                     pos[t] = -1;//切记，关键点，回溯
     33                 }
     34     }
     35 
     36     bool Danger(vector<int>pos, int t, int k) {
     37         for (int i = 0; i < t; ++i)
     38             if (pos[i] == k || abs(t - i) == abs(pos[i] - k))
     39                 return false;
     40         return true;
     41     }
     42 
     43 };
     44 
     45 
     46 //通过使用排列进行判断是否可行进行求解
     47 //但是太耗时了，还是用回溯法吧
     48 class Solution {
     49 public:
     50     vector<vector<string>> solveNQueens(int n) {
     51         vector<vector<string>>res;
     52         vector<int>nums;
     53         for (int i = 0; i < n; ++i)
     54             nums.push_back(i);
     55 
     56         if (Danger(nums)) {
     57             vector<string>v;
     58             for (int i = 0; i < n; ++i) {
     59                 string s = "";
     60                 for (int k = 0; k < nums[i]; ++k)
     61                     s += '.';
     62                 s += 'Q';
     63                 for (int k = nums[i] + 1; k < n; ++k)
     64                     s += '.';
     65                 v.push_back(s);
     66             }
     67             res.push_back(v);
     68         }
     69         while (next_permutation(nums.begin(), nums.end())) {
     70             if (Danger(nums)) {
     71                 vector<string>v;
     72                 for (int i = 0; i < n; ++i) {
     73                     string s = "";
     74                     for (int k = 0; k < nums[i]; ++k)
     75                         s += '.';
     76                     s += 'Q';
     77                     for (int k = nums[i] + 1; k < n; ++k)
     78                         s += '.';
     79                     v.push_back(s);
     80                 }
     81                 res.push_back(v);
     82             }
     83         }
     84         return res;
     85     }
     86                 
     87 
     88 
     89     bool Danger(vector<int>nums) {
        //用来判断是否可行
     90         for (int i = 0; i < nums.size(); ++i) {
     91             for (int j = 0; j < nums.size(); ++j) {
     92                 if (j == i)continue;
     93                 if ((j + nums[j]) == (i + nums[i]) || (i - nums[i]) == (j - nums[j]))
     94                     return false;
     95             }
     96         }
     97         return true;
     98     }
     99                     
    100 
    101 };
    102 
    103 
    104 void T051() {
    105     Solution s;
    106     vector<vector<string>>v;
    107     int n;
    108     n = 5;
    109     v = s.solveNQueens(n);
    110     for (auto &a : v) {
    111         for (auto b : a)
    112             cout << b << endl;
    113         cout << "//" << endl;
    114     }
    115     
    116 }

转载于:https://www.cnblogs.com/zzw1024/p/10629166.html