題目
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.
For example,There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
分析
n皇后問(wèn)題，比較經(jīng)典。沒(méi)記錯(cuò)的話應(yīng)該使用回溯法。一層層往下搜索，跳過(guò)不能放置的位置，如果個(gè)數(shù)夠了就輸出，如果搜完全圖都不夠就返回。另外對(duì)于斜線的表示，可以利用主斜線上元素的坐標(biāo)之差固定，副斜線上元素的坐標(biāo)之和固定這個(gè)性質(zhì)來(lái)判斷。
實(shí)現(xiàn)一
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
vector<string> board(n, string(n, '.'));
vector<bool> row(n, false), col(n, false);
vector<bool> md(2*n-1, false), cd(2*n-1, false);
solve(0, 0, n, ans, board, row, col, md, cd);
return ans;
}
private:
void solve(int x, int y, int nleft, vector<vector<string>> &ans,
vector<string> &board, vector<bool> &row,
vector<bool> &col, vector<bool> &md, vector<bool> &cd){
if(nleft==0){
ans.push_back(board);
return;
}
if(y>board[0].size()-1){
if(x<board.size()-1){
x++;
y = 0;
}
else{
return;
}
}
for(int i=x; i<board.size(); i++){
if(row[i]) continue;
for(int j=((i==x)?y:0); j<board[0].size(); j++){
if(col[j] || md[i-j+board.size()-1] || cd[i+j]) continue;
board[i][j] = 'Q';
row[i] = true;
col[j] = true;
md[i-j+board.size()-1] = true;
cd[i+j] = true;
solve(i, j+1, nleft-1, ans, board, row, col, md, cd);
board[i][j] = '.';
row[i] = false;
col[j] = false;
md[i-j+board.size()-1] = false;
cd[i+j] = false;
}
}
}
};
思考一
通過(guò)是通過(guò)了，但是相比別人3ms的解答，我這132ms的方法簡(jiǎn)直臘雞到我不忍直視。看了別人的代碼受到了啟發(fā)：皇后的性質(zhì)決定了棋盤的每一行有且只有一個(gè)皇后，所以直接枚舉每一行就行了。這一簡(jiǎn)單的改動(dòng)不但使得代碼更加簡(jiǎn)單了，而且讓復(fù)雜度由原來(lái)的O(n(n2))降低到了O(n^n)，直接讓程序的耗時(shí)到達(dá)了3ms。
實(shí)現(xiàn)二
思考二
由于我的代碼經(jīng)過(guò)了多次修改，所以可能不太美觀，見(jiàn)諒=_=。
