C++刷leetcode(面试题 08.12. 八皇后)【深度优先搜索】
本帖最后由 糖逗 于 2020-5-8 17:33 编辑题目描述：
设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
注意：本题相对原题做了扩展
示例:
输入：4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/eight-queens-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include<string>
#include<vector>
#include<iostream>
using namespace std;
bool valid(vector<int>& pos, int x, int y){
for(int i = 0; i < pos.size(); i++){
if(i == x || y == pos || x + y == i + pos || x + pos == y + i)return false;
}
return true;
}
void dfs(int n, int x, vector<int>& pos, vector<string>& temp, vector<vector<string> >& res){
if(x == n) res.push_back(temp);
for(int y= 0 ; y < n; y ++){
if(valid(pos, x, y)){
temp = 'Q';
pos.push_back(y);
dfs(n, x+1, pos, temp, res);
pos.pop_back();
temp = '.';
}
}
}
vector<vector<string> > solution(int n){
vector<vector<string> > res;
vector<string>temp (n, string(n, '.'));
vector<int> pos;
dfs(n, 0, pos, temp, res);
return res;
}
int main(void){
int n;
cin >> n;
vector<vector<string> > res = solution(n);
for(int i = 0; i < res.size(); i++){
for(int j = 0; j < res.size(); j++){
cout << res <<endl;
}
cout << endl;
cout << "------------------" << endl;
}
return 0;
}
参考链接：
1.x + y == i + pos || x + pos == y + i可参见链接：https://leetcode-cn.com/problems/eight-queens-lcci/solution/java-hui-su-fa-shuang-100-san-shu-zu-ji-lu-dui-jia/
页:
[1]