LeetCode51 N皇后——经典dfs+回溯（三段式解法）

 class Solution {

 public:

     // record[row]  该行对应的列

     vector<vector<string> > ans;   // 结果集

     vector<vector<string>> solveNQueens(int n) {

         string s = "";

         for(int i=; i<n; i++){

             s += '.';

         }

         vector<int> record(n);   // 记录每行对应的列

         vector<string> temp(n, s);   // 临时解，需要push到ans中

         dfs(, n, temp, record);

         return ans;

     }

     void dfs(int row, int n, vector<string> &temp, vector<int> &record){

         if(row == n){   // 到达最后一行，需要做处理，dfs出口

             ans.push_back(temp);  // 已经得到最优方案，直接返回，需要push到ans数组中。

             return;

         }

         for(int i=; i<n; i++){ // 对于每一列

             record[row] = i;

             if(isOK(record, row)){

                 // 下面三行回溯经典代码

                 temp[row][i] = 'Q';

                 dfs(row+, n, temp, record);

                 temp[row][i] = '.';   // 进行回溯！！！

             }

         }

     }

     bool isOK(vector<int> &record, int row){   // 判断row行旗子是否满足要求，三个要求画个图思考一下

         for(int i=; i<row; i++){  // 遍历row前面的每一行，是否冲突

             if(record[row] == record[i] || row - record[row]==i-record[i] ||

                row+record[row]==i+record[i])    return false;

         }

         return true;

     }

 };