经典回溯的例题
朴素方法
class Solution { public: vector<vector<string>> ans; bool check(vector<string> &cur,int row,int col)//判断是否能放皇后 { for(int i = 0; i < row; i++) if(cur[i][col] == 'Q')return false;//列 for(int i = row-1, j=col-1; i >= 0 && j >= 0; i--,j--) if(cur[i][j] == 'Q')return false;//右对角 for(int i = row-1, j=col+1; i >= 0 && j < cur.size(); i--,j++) if(cur[i][j] == 'Q')return false;//左对角 return true; } vector<vector<string>> solveNQueens(int n) { vector<string> cur(n,string(n,'.')); dfs(cur,0); return ans; } void dfs(vector<string> & cur,int row) { if(row==cur.size()) { ans.push_back(cur); return ; } for(int i=0;i<cur.size();++i) { if(check(cur,row,i)) { cur[row][i]='Q';//放皇后 dfs(cur,row+1); cur[row][i]='.';//回溯 } } } };基本思路一直没变，但储存方式却可以变换 例如可以一维数组 存放当前皇后的状态。假设数组为int col[n], col[i]表示第 i 行皇后所在的列。 新的一行 k 放置一个皇后后:
判断列，只需要看state数组中state[0…k-1] 是否有和col[k]相等； 判断对角线：如果两个皇后在同一对角线，那么|row1-row2| = |colu1 - colu2| 速度可以变得很快 第一个为使用一维数组的存储 使用位运算来求解N皇后的高效算法 https://blog.csdn.net/hackbuteer1/article/details/6657109
