【搜索与回溯算法】排队安全回家c++代码

搜索与回溯算法是一种常用的解决问题的方法，它通过穷举所有可能的解来找到问题的解。在排队安全回家的问题中，可以使用搜索与回溯算法来找到所有可能的排队方式，并判断是否存在一种方式使得每个人都能安全回家。

以下是一个使用C++实现的排队安全回家的代码示例：

#include <iostream>
#include <vector>

using namespace std;

bool isSafe(vector<int>& queue) {
    int n = queue.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // 判断是否存在逆序对
            if (queue[i] > queue[j]) {
                return false;
            }
        }
    }
    return true;
}

void backtrack(vector<int>& queue, vector<bool>& visited, vector<vector<int>>& result) {
    if (queue.size() == visited.size()) {
        if (isSafe(queue)) {
            result.push_back(queue);
        }
        return;
    }

    for (int i = 0; i < visited.size(); i++) {
        if (!visited[i]) {
            visited[i] = true;
            queue.push_back(i + 1);
            backtrack(queue, visited, result);
            queue.pop_back();
            visited[i] = false;
        }
    }
}

vector<vector<int>> findSafeQueue(int n) {
    vector<vector<int>> result;
    vector<int> queue;
    vector<bool> visited(n, false);
    backtrack(queue, visited, result);
    return result;
}

int main() {
    int n;
    cout << "请输入排队的人数：";
    cin >> n;

    vector<vector<int>> result = findSafeQueue(n);

    cout << "所有安全的排队方式：" << endl;
    for (const auto& queue : result) {
        for (int i = 0; i < queue.size(); i++) {
            cout << queue[i];
            if (i != queue.size() - 1) {
                cout << " -> ";
            }
        }
        cout << endl;
    }

    return 0;
}

这段代码中，`isSafe`函数用于判断一个排队方式是否安全，`backtrack`函数用于回溯搜索所有可能的排队方式，`findSafeQueue`函数是入口函数，用于调用回溯函数并返回所有安全的排队方式。