c++写一个路径数组的自交叉检测函数

在 C++ 中，创建一个检测路径数组是否自相交的函数需要一些空间复杂度的考虑，因为我们需要存储部分路径以比较它们。这里是一个简单的例子，我们假设输入的是二维整数数组，代表网格中的方向变化（0表示不动，1表示向右，2表示向下）。我们可以使用哈希集合（如 std::unordered_set）来跟踪已经访问过的节点，如果发现重复，则说明路径有自交叉。

#include <vector>
#include <unordered_set>

bool isPathCrossed(std::vector<std::pair<int, int>>& path) {
    std::unordered_set<std::pair<int, int>> visited;
    int x = path[0].first, y = path[0].second;
    visited.insert({x, y});

    for (const auto& step : path) {
        int dx = step.first - x;
        int dy = step.second - y;
        
        if (dx == 1 && dy == 0) { // 向右
            x++;
        } else if (dx == -1 && dy == 0) { // 向左
            x--;
        } else if (dx == 0 && dy == 1) { // 向下
            y++;
        } else if (dx == 0 && dy == -1) { // 向上
            y--;
        } else {
            return true; // 非法移动，直接返回交叉
        }

        if (!visited.count({x, y})) {
            visited.insert({x, y});
        } else {
            return true; // 发现重复点，路径交叉
        }
    }

    return false; // 如果遍历完整个路径都没有重复，说明没有交叉
}

// 示例用法
int main() {
    std::vector<std::pair<int, int>> path = {{0, 0}, {1, 0}, {2, 0}, {2, 1}};
    if (isPathCrossed(path)) {
        std::cout << "Path has a crossing." << std::endl;
    } else {
        std::cout << "Path does not have a crossing." << std::endl;
    }
    return 0;
}