阅读量:0
使用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，用于存储当前皇后的位置。当找到一个解时，我们将其打印出来。
