如何使用c++ stack类实现回溯算法

使用C++的stack类实现回溯算法，首先需要了解回溯算法的基本概念。回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解的话（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。

这里是一个使用C++ stack类实现回溯算法的简单示例：

问题：八皇后问题

#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的递归函数来实现回溯算法。stk是一个pair类型的stack，用于存储当前皇后的位置。当找到一个解时，我们将其打印出来。