013.N皇后-創(chuàng)新互聯(lián)

1.題目鏈接：

51. N 皇后

創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的阿瓦提網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！2.解題思路：

2.1.題目要求：

給一個(gè)數(shù)字 n ，要求返回所有 n 個(gè) 皇后能在 n X n 的棋盤(pán)上不相互攻擊的情況。

能攻擊到的情況：以皇后自身為原點(diǎn)，橫、豎、同斜線（45度、135度）都可以被攻擊到。

下圖為n=4的時(shí)候，4 個(gè)皇后在 4 X 4 棋盤(pán)的所有生存情況。

2.2.思路：

處理本體，要求對(duì)二維數(shù)組進(jìn)行處理，for循環(huán)的 i 當(dāng)作橫軸，然后再自建一個(gè)縱軸row，就可以遍歷整個(gè)棋盤(pán)了，每走一步就判斷一次，該皇后位置對(duì)其他皇后位置的威脅，有威脅繼續(xù)遍歷，沒(méi)有就把皇后落在這里，終止條件就是到葉子節(jié)點(diǎn)

2.3.回溯三部曲：

col == column == 縱行 y

2.3.1.確定回溯函數(shù)參數(shù)

需要一個(gè) row + for循環(huán)的col( i ) 來(lái)遍歷棋盤(pán)

vector>result;
void backtracking(int n, int row, vector& chessboard) {

2.3.2.確定終止條件

if (row == n) {
    result.push_back(chessboard);
    return;
}

2.3.3.確定單層遍歷邏輯

判斷皇后Q再在這位置合不合適，合適落點(diǎn)繼續(xù)遍歷，不合適繼續(xù)找合適的

for (int col = 0; col< n; col++) {
    if (isValid(row, col, chessboard, n)) { // 驗(yàn)證合法就可以放
        chessboard[row][col] = 'Q'; // 放置皇后
        backtracking(n, row + 1, chessboard);
        chessboard[row][col] = '.'; // 回溯，撤銷(xiāo)皇后
    }
}

2.3.4.如何判斷皇后在當(dāng)前位置和其他皇后會(huì)不會(huì)沖突？

按照如下標(biāo)準(zhǔn)判斷：

不能同行
不能同列
不能同斜線（45度和135度角）

行沒(méi)有判斷是因?yàn)閒or循環(huán)，一行只放一個(gè)皇后的，直接滿足了皇后不能在同一行的規(guī)則。

代碼如下：

bool isValid(int row, int col, vector& chessboard, int n) {
    // 檢查列
    for (int i = 0; i< row; i++) { // 這是一個(gè)剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // 檢查 45度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 檢查 135度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j< n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

2.4.總代碼：

class Solution {
private:
vector>result;
// n 為輸入的棋盤(pán)大小
// row 是當(dāng)前遞歸到棋盤(pán)的第幾行了
void backtracking(int n, int row, vector& chessboard) {
    if (row == n) {
        result.push_back(chessboard);
        return;
    }
    for (int col = 0; col< n; col++) {
        if (isValid(row, col, chessboard, n)) { // 驗(yàn)證合法就可以放
            chessboard[row][col] = 'Q'; // 放置皇后
            backtracking(n, row + 1, chessboard);
            chessboard[row][col] = '.'; // 回溯，撤銷(xiāo)皇后
        }
    }
}
bool isValid(int row, int col, vector& chessboard, int n) {
    // 檢查列
    for (int i = 0; i< row; i++) { // 這是一個(gè)剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // 檢查 45度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 檢查 135度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j< n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
public:
    vector>solveNQueens(int n) {
        result.clear();
        std::vectorchessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);
        return result;
    }
};

3.遇見(jiàn)的問(wèn)題：

怎么 row == n 就返回了呢？

（按我的理解，這個(gè)時(shí)候還沒(méi)遍歷完Q（皇后）在row == n 這一行的可能性，直接返回，那不完整?。?/p>

哦哦，他進(jìn)入第一次遞歸狀態(tài)的時(shí)候才 row 才+1，如下圖，當(dāng)搜索最后一層的 row == 2 的時(shí)候，因?yàn)?row == 3 才停止搜索，所以還會(huì)繼續(xù)向下遞歸，繼續(xù)遞歸 row +1 ，觸發(fā)終止條件，返回。

沒(méi)有返回方案失敗的情況嗎？

（n = 3，放置會(huì)失敗，代碼里感覺(jué)好像沒(méi)有對(duì)應(yīng)的情況）
題目要求返回方案...那返回的方案不完整也就是意思是無(wú)解的意思吧..這樣理解好了。

確認(rèn)皇后45度和135度的代碼怎么理解？

（感覺(jué)判斷皇后在當(dāng)前位置合不合適的代碼看不懂啊，45度和135度哪里，可能現(xiàn)在腦子有點(diǎn)不好使，下次來(lái)看）
哦哦，代碼只往皇后的135度和45度上查，因?yàn)橹挥猩厦娌庞谢屎?，下面還沒(méi)去放皇后，因?yàn)樯厦孢€沒(méi)放好。
（先入為主了，還是把條件列清楚，畫(huà)個(gè)圖合適）

C++中的std::是什么？

std:: 是個(gè)名稱(chēng)空間標(biāo)示符，C++標(biāo)準(zhǔn)庫(kù)中的函數(shù)或者對(duì)象都是在命名空間std中定義的，所以我們要使用標(biāo)準(zhǔn)函數(shù)庫(kù)中的函數(shù)或?qū)ο蠖家褂胹td來(lái)限定。
（命名的時(shí)候刪掉都可以通過(guò)，所以干嘛加這玩意...）

4.記錄：

不用太貪，處理完N皇后先，感覺(jué)前面那道飛機(jī)也可以處理，題目理解了，不過(guò)要去學(xué)map和set。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞標(biāo)題：013.N皇后-創(chuàng)新互聯(lián)
鏈接分享：http://weahome.cn/article/ddghcj.html

真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

013.N皇后-創(chuàng)新互聯(lián)

其他資訊

網(wǎng)站制作

企業(yè)服務(wù)

網(wǎng)站建設(shè)

服務(wù)器托管