算法(回溯)-n皇后问题
该题主要来自于力扣。算法主要使用了回溯的算法思想,该题的相关代码思路来自于代码随想录的carl哥。
https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html#%E6%80%9D%E8%B7%AF
题目描述
https://leetcode.cn/problems/n-queens/description/
题目解析:
该题主要使用了回溯法,而且,n皇后问题要求所有皇后不在同一行,同一列,同一斜线。因此我们把整个棋盘看作一个树。
在每一层不断循环,往下一行则是模拟树枝向下的过程,逐渐递归。结束该层某个元素之后,就进行回溯。
相对来说思路比较简单,主要是需要一个验证当前位置是否合法的isvalid函数。
代码解析:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| class Solution { vector<vector<string>> result; private: void huisu(int n,int row,vector<string>& checkpoint){ if(n==row){ result.push_back(checkpoint); return; } for(int i=0;i<n;i++){ if(isvalid(n,i,row,checkpoint)){//n是总行数列数,i是当前列数,row是当前行数 checkpoint[row][i]='Q'; huisu(n,row+1,checkpoint); checkpoint[row][i]='.'; } } } bool isvalid(int n ,int col ,int row , vector<string> checkpoint){ for(int i=0;i<row;i++){ if(checkpoint[i][col]=='Q'){ return false; } } //45度 for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){ if(checkpoint[i][j]=='Q'){ return false; } } //135度 for(int i=row-1, j=col+1;i>=0&&j<n;i--,j++){ if(checkpoint[i][j]=='Q'){ return false; } } return true; } public: vector<vector<string>> solveNQueens(int n) { std::vector<std::string> checkpoint(n,std::string(n,'.')); result.clear(); huisu(n,0,checkpoint); return result; } };
|
注意初始化checkpoint的时候,要使用相关stl的构造函数。
整体上该题思路不是很难。