今日学习记录
1. 52. N 皇后 II
关键词：回溯
问题分析：
经典皇后问题,横竖斜都不能同时存在超过一个皇后
核心思路:
dfs+回溯
很简单的一道题,就是记录四个方向(斜是两个反向,包括正对角线和副对角线),首先是一个小关键,一个 nxn 的棋盘中要放 n 个棋子,其中每行都只能放一个棋子且必须放一个棋子,然后就是对角线的记录,学过矩阵的我们知道,x 和 y 是可以计算出对角线的特值的
- 对于正对角线: x+y
- 对于副对角线: x-y+n-1
再从零开始 dfs,其实就是选和不选,只是计数方式不同,对于每一行都去遍历然后选择
选了之后不能就直接选了,我们还要回溯到上一次没选的地方找其他的地方
dfs 的状态为
当前放置的棋子数,当等于 n 时结束递归并使 ans 加一
**最终代码：
int totalNQueens(int n) {
vector<int> cl(n,0);
vector<int> dui1(20,0);
vector<int> dui2(20,0);
int ans = 0;
//s相当于纵坐标,i相当于横坐标
auto dfs = [&](this auto&&dfs,int s){
if(s==n){
ans++;
return;
}
for(int i = 0;i<n;i++){
if(!cl[i]&&!dui1[s-i+n-1]&&!dui2[s+i]){
cl[i] = dui1[s-i+n-1] = dui2[s+i] = 1;
dfs(s+1);
cl[i] = dui1[s-i+n-1] = dui2[s+i] = 0;
}
}
};
dfs(0);
return ans;
}学到的点： 1.
2. 51. N 皇后
核心思路 一样的方法,只需要额外维护一个字符串的数组来记录每次的答案就行,满足条件的时候不再是将答案加一而是把这个符合条件的数组放入最终答案数组中 最终代码：
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
vector arr(n,string(n,'.'));
vector<int> cl(n,0);
vector<int> dui1(20,0);
vector<int> dui2(20,0);
//s相当于纵坐标,i相当于横坐标
auto dfs = [&](this auto&&dfs,int s){
if(s==n){
ans.push_back(arr);
return;
}
for(int i = 0;i<n;i++){
if(!cl[i]&&!dui1[s-i+n-1]&&!dui2[s+i]){
cl[i] = dui1[s-i+n-1] = dui2[s+i] = 1;
arr[s][i] = 'Q';
dfs(s+1);
arr[s][i] = '.';
cl[i] = dui1[s-i+n-1] = dui2[s+i] = 0;
}
}
};
dfs(0);
return ans;
}学到的点：
- 回溯