回溯法,主要应用在dfs中,主要思想是当你push一个元素后,记住要pop回去,大致的模板是
path.push_back(nums[i]);
dfs(pos+1);
path.pop();
详细的模板在我们之前用回溯法解决全排列问题有提到。
2 N皇后问题2n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。 给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
思路:标准的dfs模板套路,只是要判断位置是否合法,自己编写一个函数判断。刚开始全都初始化为’.’,我们dfs时是逐行递归,在dfs中判断在pos那一行中的哪一列进行插入,这里需要一个isvalid(row,col)函数进行判断位置是否合法,判断时分为四部分,行,列,对角线,反对角线进行判断是否有’Q’。
class Solution {
public:
vector<vector> ans;
vector list;
bool isvalid(int row,int col, int n)
{
//逐行判断
for(int j=0;j<n;j++)
{
if(list[row][j]=='Q')
return false;
}
//逐列判断
for(int i=0;i<n;i++)
{
if(list[i][col]=='Q')
return false;
}
for(int k=1;k<=min(row,col);k++)
{
if(list[row-k][col-k]=='Q')
return false;
}
for(int k=1;k<=min(row,n-1-col);k++)
{
if(list[row-k][col+k]=='Q')
return false;
}
return true;
}
void dfs(int pos,int n)
{
if(pos==n)
{
ans.push_back(list);
return ;
}
for(int j=0;j<n;j++){
if(isvalid(pos,j,n))
{
list[pos][j]='Q';
dfs(pos+1,n);
list[pos][j]='.';
}
}
}
vector<vector> solveNQueens(int n) {
list.assign(n,string(n,'.'));
dfs(0,n);
return ans;
}
3 N皇后问题1
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
N皇后问题1可以理解为问题2的简化版,不要求输出结果,只输出方案数,方法与2类似,其实还有更简单的方法,进行位运算判断位置是否合法,但比较难理解。
class Solution {
public:
//逐行进行dfs,再dfs中,在逐列进行判断
int ans;
vector list;
bool ifvalid(int row,int col,int n)
{
//先对这一行进行判断
for(int j=0; j<n; j++)
{
//判断如果这一行有皇后
if(list[row][j]=='Q')
return false;
}
//对这一列进行判断
for(int i=0; i<n; i++)
{
//判断如果这一行有皇后
if(list[i][col]=='Q')
return false;
}
/*对角线 \ */
for(int i=1; i<=min(row,col); i++)
{
//判断如果这一行有皇后
if(list[row-i][col-i]=='Q')
return false;
}
//反对角线 /
for(int i=1; i<=min(row,n-1-col); i++)
{
//判断如果这一行有皇后
if(list[row-i][col+i]=='Q')
return false;
}
return true;
}
void dfs(int n,int pos)
{
if(pos==n)
{
ans++;
return;
}
for(int j=0;j<n;j++)
{
if(ifvalid(pos,j,n))//判断这个位置是否合法
{
list[pos][j]='Q';//对称的回溯
dfs(n,pos+1);
list[pos][j]='.';
}
}
}
int totalNQueens(int n) {
list.assign (n, string(n, '.'));
dfs(n,0);
return ans;
}
};
Sunlight..
原创文章 14获赞 10访问量 423
关注
私信
展开阅读全文