C++實(shí)現(xiàn)LeetCode(51.N皇后問題)
[LeetCode] 51. N-Queens N皇后問題
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.
經(jīng)典的N皇后問題，基本所有的算法書中都會(huì)包含的問題?？赡苡行┤藢H象棋不太熟悉，大家都知道中國象棋中最叼的是車，橫豎都能走，但是在國際象棋中還有更叼的，就是皇后，不但能橫豎走，還能走兩個(gè)斜線，有如 bug 一般的存在。所以經(jīng)典的八皇后問題就應(yīng)運(yùn)而生了，在一個(gè) 8x8 大小的棋盤上如果才能放8個(gè)皇后，使得兩兩之間不能相遇，所謂一山不能容二虎，而這里有八個(gè)母老虎，互相都不能相遇。對于這類問題，沒有太簡便的方法，只能使用窮舉法，就是嘗試所有的組合，每放置一個(gè)新的皇后的時(shí)候，必須要保證跟之前的所有皇后不能沖突，若發(fā)生了沖突，說明當(dāng)前位置不能放，要重新找地方，這個(gè)邏輯非常適合用遞歸來做。我們先建立一個(gè)長度為 nxn 的全是點(diǎn)的數(shù)組 queens，然后從第0行開始調(diào)用遞歸。在遞歸函數(shù)中，我們首先判斷當(dāng)前行數(shù)是否已經(jīng)為n，是的話，說明所有的皇后都已經(jīng)成功放置好了，所以我們只要將 queens 數(shù)組加入結(jié)果 res 中即可。否則的話，我們遍歷該行的所有列的位置，行跟列的位置都確定后，我們要驗(yàn)證當(dāng)前位置是否會(huì)產(chǎn)生沖突，那么就需要使用一個(gè)子函數(shù)來判斷了，首先驗(yàn)證該列是否有沖突，就遍歷之前的所有行，若某一行相同列也有皇后，則沖突返回false；再驗(yàn)證兩個(gè)對角線是否沖突，就是一些坐標(biāo)轉(zhuǎn)換，主要不要寫錯(cuò)了，若都沒有沖突，則說明該位置可以放皇后，放了新皇后之后，再對下一行調(diào)用遞歸即可，注意遞歸結(jié)束之后要返回狀態(tài)，參見代碼如下：
解法一：
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;
}
};
我們還可以只使用一個(gè)一維數(shù)組 queenCol 來保存所有皇后的列位置，初始化均為-1， 那么 queenCol[i] 就是表示第i個(gè)皇后在 (i, queenCol[i]) 位置，遞歸函數(shù)還是跟上面的解法相同，就是在當(dāng)前行數(shù)等于n的時(shí)候，我們要將 queenCol 還原成一個(gè) nxn 大小的矩陣，并存入結(jié)果 res 中。這種記錄每個(gè)皇后的坐標(biāo)的方法在驗(yàn)證沖突的時(shí)候比較簡單，只要從第0行遍歷到當(dāng)前行，若跟之前的皇后的列數(shù)相同，直接返回false，叼就叼在判斷對角線沖突非常簡便，因?yàn)楫?dāng)兩個(gè)點(diǎn)在同一條對角線上，那么二者的橫坐標(biāo)差的絕對值等于縱坐標(biāo)差的絕對值，利用這條性質(zhì)，可以快速的判斷沖突，代碼如下：
解法二：
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;
}
};
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(51.N皇后問題)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)N皇后問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- C++實(shí)現(xiàn)LeetCode(94.二叉樹的中序遍歷)
- C++實(shí)現(xiàn)LeetCode(112.二叉樹的路徑和)
- C++實(shí)現(xiàn)LeetCode(78.子集合)
- C++實(shí)現(xiàn)LeetCode(47.全排列之二)
- C++實(shí)現(xiàn)LeetCode(90.子集合之二)
- C++實(shí)現(xiàn)LeetCode(113.二叉樹路徑之和之二)
- C++實(shí)現(xiàn)LeetCode(39.組合之和)
- C++實(shí)現(xiàn)LeetCode(38.計(jì)數(shù)和讀法)
- C++實(shí)現(xiàn)LeetCode(77.Combinations 組合項(xiàng))
- C++實(shí)現(xiàn)LeetCode(46.全排列)
- C++實(shí)現(xiàn)LeetCode(43.字符串相乘)
相關(guān)文章
詳解QListWidget如何實(shí)現(xiàn)自定義Item效果
這篇文章主要為大家介紹了如何通過QListWidget實(shí)現(xiàn)自定義Item效果，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起了解一下2022-04-04
C語言動(dòng)態(tài)分配二維字符串?dāng)?shù)組的方法
小編最近忙里偷閑，給大家整理一份教程關(guān)于C語言動(dòng)態(tài)分配二維字符串?dāng)?shù)組的方法，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友參考下吧2021-10-10
C/C++實(shí)現(xiàn)高并發(fā)http服務(wù)器的代碼示例
這篇文章簡單給大家介紹了C/C++實(shí)現(xiàn)高并發(fā)http服務(wù)器的代碼示例，文章通過代碼和圖文介紹的非常詳細(xì)，感興趣的同學(xué)可以參考閱讀2023-07-07
C語言中用棧+隊(duì)列實(shí)現(xiàn)隊(duì)列中的元素逆置
這篇文章主要介紹了C語言中用利用棧和隊(duì)列實(shí)現(xiàn)隊(duì)列中的元素逆置的相關(guān)資料，對正在學(xué)習(xí)的小伙伴有一定的參考價(jià)值，需要的可以參考一下，希望對你有所幫助2022-02-02
C++貪心算法實(shí)現(xiàn)活動(dòng)安排問題(實(shí)例代碼)
貪心算法（又稱貪婪算法）是指，在對問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。這篇文章主要介紹了C++貪心算法實(shí)現(xiàn)活動(dòng)安排問題,需要的朋友可以參考下2019-11-11
下面小編就為大家?guī)硪黄嘘P(guān)C++頭文件的包含順序研究。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-01-01
Visual C++ 常用數(shù)據(jù)類型轉(zhuǎn)換方法詳解
本文純粹是總結(jié)一下有關(guān)類型轉(zhuǎn)換的貼子,需要的朋友可以參考下2017-06-06
這篇文章主要介紹了如何把C++的源代碼改寫成C代碼,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-07-07
C語言動(dòng)態(tài)內(nèi)存函數(shù)詳解
這篇文章主要介紹了C語言動(dòng)態(tài)內(nèi)存函數(shù)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-09-09
這篇文章主要給大家介紹了關(guān)于C++運(yùn)算符重載的一些困惑，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04