Leetcode: N-Queens C++

 1 class Solution {
 2 public:
 3     vector<vector<string> > solveNQueens(int n) {
 4      vector<vector<string>> res;
 5      vector<vector<string>> pre_res;
 6      for(int i = 0; i < n; i++){
 7          res.clear();
 8          for(int j = 0; j < n; j++){
 9              if(i == 0){
10                  vector<string> tmp;
11                  string s;
12                  s.assign(n,.);
13                  s[j] = Q;
14                  tmp.push_back(s);
15                  res.push_back(tmp);
16              }else{
17                  for(int k = 0; k < pre_res.size(); k++){
18                      if(not_attack(pre_res[k],i,j,n)){
19                          string s;
20                          s.assign(n,.);
21                          s[j] = Q;
22                          vector<string> tmp;
23                          tmp = pre_res[k];
24                          tmp.push_back(s);
25                          res.push_back(tmp);
26                      }
27                  }
28                  
29              }
30          }
31          pre_res = res;
32      }
33      return pre_res;   
34     }
35     bool not_attack(vector<string> cb, int row,int col, int n){
36         int i = 0;
37         while(i < row){
38             if(cb[i][col] == Q) return false;
39             i++;
40         }
41         i = row - 1;
42         int j = col - 1;
43         while(i >= 0 && j >= 0){
44             if(cb[i][j] == Q) return false;
45             i--;
46             j--;
47         }
48         i = row - 1;
49         j = col + 1;
50         while(i >= 0 && j < n){
51             if(cb[i][j] == Q) return false;
52             i--;
53             j++;
54         }
55         return true;
56     }
57 };

 

Leetcode: N-Queens C++,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。