N 皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1:
输入:n = 4 输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1 提示:输出:[["Q"]]
提示:
1 <= n <= 9
- 皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。
以下程序实现了这一功能,请你填补空白处的内容:
#include <bits/stdc++.h> using namespace std; class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<vector<string>> res; vector<int> stack(n); vector<string> solution(n, string(n, '.')); dfs(n, 0, stack, solution, res); return res; } private: void dfs(int n, int row, vector<int> &stack, vector<string> &solution, vector<vector<string>> &res) { if (row == n) { res.push_back(solution); } else { for (int i = 0; i < n; i++) { if (row == 0 || !conflict(stack, row, i)) { solution[row][i] = 'Q'; stack[row] = i; dfs(n, row + 1, stack, solution, res); solution[row][i] = '.'; } } } } bool conflict(vector<int> &stack, int row, int col) { for (int i = 0; i < row; i++) { if (col == stack[i] || abs(row - i) == abs(col - stack[i])) { return true; } } return false; } }