题目地址

https://leetcode.com/problems/n-queens/

题目描述

The n -queens puzzle is the problem of placing n queens on an n × n chessboard such that no two queens attack each other.

Given an integer n , return all distinct solutions to the n -queens puzzle.

Each solution contains a distinct board configuration of the n -queens' placement, where `'Q'` and `'.'` both indicate a queen and an empty space respectively.

Example:

``````Input: 4
Output: [
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
``````

代码

``````class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> queens(n, string(n, '.'));
helper(0, queens, res);
return res;
}
void helper(int curRow, vector<string>& queens, vector<vector<string>>& res) {
int n = queens.size();
if (curRow == n) {
res.push_back(queens);
return;
}
for (int i = 0; i < n; ++i) {
if (isValid(queens, curRow, i)) {
queens[curRow][i] = 'Q';
helper(curRow + 1, queens, res);
queens[curRow][i] = '.';
}
}
}
bool isValid(vector<string>& queens, int row, int col) {
for (int i = 0; i < row; ++i) {
if (queens[i][col] == 'Q') return false;
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
if (queens[i][j] == 'Q') return false;
}
for (int i = row - 1, j = col + 1; i >= 0 && j < queens.size(); --i, ++j) {
if (queens[i][j] == 'Q') return false;
}
return true;
}
};

``````

``````class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<int> queenCol(n, -1);
helper(0, queenCol, res);
return res;
}
void helper(int curRow, vector<int>& queenCol, vector<vector<string>>& res) {
int n = queenCol.size();
if (curRow == n) {
vector<string> out(n, string(n, '.'));
for (int i = 0; i < n; ++i) {
out[i][queenCol[i]] = 'Q';
}
res.push_back(out);
return;
}
for (int i = 0; i < n; ++i) {
if (isValid(queenCol, curRow, i)) {
queenCol[curRow] = i;
helper(curRow + 1, queenCol, res);
queenCol[curRow] = -1;
}
}
}
bool isValid(vector<int>& queenCol, int row, int col) {
for (int i = 0; i < row; ++i) {
if (col == queenCol[i] || abs(row - i) == abs(col - queenCol[i])) return false;
}
return true;
}
};
``````

评论
0 评论