溫馨提示×

如何使用c++ stack類實現(xiàn)回溯算法

c++
小樊
81
2024-09-25 08:44:17
欄目: 編程語言

使用C++的stack類實現(xiàn)回溯算法，首先需要了解回溯算法的基本概念?；厮菟惴ㄊ且环N通過探索所有可能的候選解來找出所有解的算法。如果候選解被確認不是一個解的話（或者至少不是最后一個解），回溯算法會通過在上一步進行一些變化拋棄該解，即回溯并且再次嘗試。

這里是一個使用C++ stack類實現(xiàn)回溯算法的簡單示例：

問題：八皇后問題

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

bool isValid(vector<vector<int>>& board, int row, int col) {
    for (int i = 0; i < col; i++) {
        if (board[row][i] == 1) {
            return false;
        }
    }

    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1) {
            return false;
        }
    }

    for (int i = row - 1, j = col + 1; i >= 0 && j < board.size(); i--, j++) {
        if (board[i][j] == 1) {
            return false;
        }
    }

    return true;
}

void solveNQueensUtil(vector<vector<int>>& board, int col, stack<pair<int, int>>& stk) {
    if (col >= board.size()) {
        cout << "Solution exists." << endl;
        return;
    }

    for (int row = 0; row < board.size(); row++) {
        if (isValid(board, row, col)) {
            board[row][col] = 1;
            stk.push({row, col});

            solveNQueensUtil(board, col + 1, stk);

            board[row][col] = 0;
            stk.pop();
        }
    }
}

void printBoard(vector<vector<int>>& board) {
    for (const auto& row : board) {
        for (int cell : row) {
            cout << cell << " ";
        }
        cout << endl;
    }
}

int main() {
    vector<vector<int>> board(8, vector<int>(8, 0));
    stack<pair<int, int>> stk;

    solveNQueensUtil(board, 0, stk);
    printBoard(board);

    return 0;
}

在這個示例中，我們使用了一個名為solveNQueensUtil的遞歸函數(shù)來實現(xiàn)回溯算法。stk是一個pair類型的stack，用于存儲當前皇后的位置。當找到一個解時，我們將其打印出來。

0 踩