C++刷leetcode(面试题 08.12. 八皇后)【深度优先搜索】

糖逗

题目描述：

1. 设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
   
2. 
   
3. 注意：本题相对原题做了扩展
   
4. 
   
5. 示例:
   
6. 
   
7. 输入：4
   
8. 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
   
9. 解释: 4 皇后问题存在如下两个不同的解法。
   
10. [
    
11.  [".Q..",  // 解法 1
    
12.   "...Q",
    
13.   "Q...",
    
14.   "..Q."],
    
15. 
    
16.  ["..Q.",  // 解法 2
    
17.   "Q...",
    
18.   "...Q",
    
19.   ".Q.."]
    
20. ]
    
21. 
    
22. 来源：力扣（LeetCode）
    
23. 链接：https://leetcode-cn.com/problems/eight-queens-lcci
    
24. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include<string>
   
2. #include<vector>
   
3. #include<iostream>
   
4. 
   
5. using namespace std;
   
6. 
   
7. bool valid(vector<int>& pos, int x, int y){
   
8.         for(int i = 0; i < pos.size(); i++){
   
9.                 if(i == x || y == pos[i] || x + y == i + pos[i] || x + pos[i] == y + i)return false;
   
10.                
    
11.         }
    
12.         return true;
    
13. }
    
14. 
    
15. 
    
16. 
    
17. void dfs(int n, int x, vector<int>& pos, vector<string>& temp, vector<vector<string> >& res){
    
18.         if(x == n) res.push_back(temp);
    
19.         for(int y= 0 ; y < n; y ++){
    
20.                 if(valid(pos, x, y)){
    
21.                         temp[x][y] = 'Q';
    
22.                         pos.push_back(y);
    
23.                         dfs(n, x+1, pos, temp, res);
    
24.                         pos.pop_back();
    
25.                         temp[x][y] = '.';
    
26.                 }       
    
27.         }
    
28. }
    
29. 
    
30. 
    
31. 
    
32. vector<vector<string> > solution(int n){
    
33.         vector<vector<string> > res;
    
34.         vector<string>temp (n, string(n, '.'));
    
35.         vector<int> pos;
    
36.         dfs(n, 0, pos, temp, res);
    
37.         return res;
    
38. }
    
39. 
    
40. 
    
41. 
    
42. 
    
43. int main(void){
    
44.         int n;
    
45.         cin >> n;
    
46.         vector<vector<string> > res = solution(n);
    
47.         for(int i = 0; i < res.size(); i++){
    
48.                 for(int j = 0; j < res[i].size(); j++){
    
49.                         cout << res[i][j] <<  endl;
    
50.                 }
    
51.                 cout << endl;
    
52.                 cout << "------------------" << endl;
    
53.         }
    
54.         return 0;
    
55. }
    

复制代码

参考链接：
1.x + y == i + pos[i] || x + pos[i] == y + i  可参见链接：https://leetcode-cn.com/problems ... u-zu-ji-lu-dui-jia/