LeetCode51. N 皇后

题目

分析

依旧回溯的模板题，要看出每次检查一个table，搜索树的元素是table

代码

 1 class Solution {
 2 public:
 3     vector<vector<string>>res;
 4     
 5     bool check(int row,int col,vector<string>table,int n){
 6         //检查同一列
 7         for(int i = 0;i < row;i++){
 8             if(table[i][col] == 'Q')
 9                 return false;
10         }
11         //检查同一行
12         for(int j = 0;j < col;j++){
13             if(table[row][j] == 'Q')
14                 return false;
15         }
16         //因为回溯是从上到下，从左往右，所以不必检查左下角，右下角
17         //检查左上角
18         for(int i = row - 1,j = col - 1;i>=0 && j>=0;i--,j--){
19             if(table[i][j] == 'Q')
20                 return false;
21         }
22         //检查右上角
23         for(int i = row -1,j = col + 1;i >=0 && j < n;i--,j++){
24             if(table[i][j] == 'Q')
25                 return false;
26         }
27         return true;
28     }
29     void backtracking(int n,int row,vector<string>& table){
30         if(row == n){
31             res.push_back(table);
32             return;
33         }
34         for(int col = 0;col < n;col++){
35             if(check(row,col,table,n)){
36                 table[row][col] = 'Q';
37                 backtracking(n,row+1,table);
38                 table[row][col] = '.';
39             }
40         }
41     }
42     vector<vector<string>> solveNQueens(int n) {
43         vector<string>table(n,string(n,'.')); //定义一个table
44         backtracking(n,0,table);
45         return res;
46     }
47 };

注意如何定义一个table，容器还是不熟