- N 皇后
题目链接:N皇后
题目
思路
用回溯方法,先构造出一个棋盘二维数组,每行选择一个位置放皇后Q,再不断回溯,
代码
class Solution {
vector<vector<string>> res;
bool isN(vector<string> &path,int row,int col,int n)
{ //只需要考虑row行以上的位置
//看同一列的位置
for(int i=0;i<row;i++)
{
if(path[i][col]=='Q') return false;
}
//右上角一斜线上的
for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++)
{
if(path[i][j]=='Q') return false;
}
//左上角一斜线上的
for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--)
{
if(path[i][j]=='Q') return false;
}
return true;
}
void helper(int n,int row,vector<string> &path)
{
if(row==n) //n个皇后已经摆好一个棋盘,满足一个答案的条件
{
res.push_back(path);
return;
}
for(int col=0; col<n; col++)
{
if(isN(path,row,col,n) )
{
path[row][col]='Q';//每行选择一个Q
helper(n,row+1,path);
path[row][col]='.';
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
//第一种string构造方法
string s1 ;
for(int i=0;i<n; i++)
{
s1.push_back('.');
}
//string s1(n,'.'); //第二种构造string方法
vector<string> path(n,s1);
helper(n,0,path);
return res;
}
};