c++ jps优化 完整代码

c jps（Jump Point Search）是一种寻路算法，用于在给定的网格中找到两个节点间的最短路径。它通过剪枝的方式避免搜索不必要的节点，从而提高搜索速度。下面是c jps的优化完整代码：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 定义节点的数据结构
struct Node {
    int x, y;
    int g, h;
    Node* parent;
    
    Node(int _x, int _y, int _g, int _h, Node* _parent) {
        x = _x;
        y = _y;
        g = _g;
        h = _h;
        parent = _parent;
    }
    
    int f() {
        return g + h;
    }
};

// 判断节点是否在网格内
bool isValid(int x, int y, int rows, int cols) {
    return (x >= 0 && x < rows && y >= 0 && y < cols);
}

// 判断节点是否是障碍
bool isObstacle(vector<vector<int>>& grid, int x, int y) {
    return (grid[x][y] == 1);
}

// 计算节点间的曼哈顿距离
int manhattanDistance(int x1, int y1, int x2, int y2) {
    return abs(x2 - x1) + abs(y2 - y1);
}

// 判断是否可以跳跃到某个方向
bool hasForcedNeighbor(vector<vector<int>>& grid, int x, int y, int dx, int dy) {
    int newX = x + dx;
    int newY = y + dy;
    
    if (!isValid(newX, newY, grid.size(), grid[0].size()) || isObstacle(grid, newX, newY)) {
        return false;
    }
    
    if (dx != 0 && dy != 0) {
        if ((isObstacle(grid, x + dx, y + dy - dy) && !isObstacle(grid, x + dx, y)) || 
            (isObstacle(grid, x + dx - dx, y + dy) && !isObstacle(grid, x, y + dy))) {
            return true;
        }
    }
    return false;
}

// 执行JPS算法
vector<pair<int, int>> jps(vector<vector<int>>& grid, int startX, int startY, int endX, int endY) {
    vector<pair<int, int>> path;
    
    int rows = grid.size();
    int cols = grid[0].size();
    
    vector<vector<Node*>> nodes(rows, vector<Node*>(cols, nullptr));
    
    priority_queue<Node*, vector<Node*>, function<bool(Node*, Node*)>> openList(
        [](Node* a, Node* b) {
            return a->f() > b->f();
        }
    );
    
    // 初始化起始节点
    Node* start = new Node(startX, startY, 0, manhattanDistance(startX, startY, endX, endY), nullptr);
    nodes[startX][startY] = start;
    
    openList.push(start);
    
    while (!openList.empty()) {
        Node* curr = openList.top();
        openList.pop();
        
        if (curr->x == endX && curr->y == endY) {
            // 找到了终点，构造并返回路径
            while (curr != nullptr) {
                path.push_back(make_pair(curr->x, curr->y));
                curr = curr->parent;
            }
            break;
        }
        
        int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
        int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
        
        for (int i = 0; i < 8; i++) {
            int newX = curr->x + dx[i];
            int newY = curr->y + dy[i];
            
            if (!isValid(newX, newY, rows, cols) || isObstacle(grid, newX, newY)) {
                continue;
            }
            
            int newG = curr->g + manhattanDistance(curr->x, curr->y, newX, newY);
            int newH = manhattanDistance(newX, newY, endX, endY);
            
            Node* neighbor = nodes[newX][newY];
            
            if (neighbor == nullptr || newG < neighbor->g) {
                if (neighbor == nullptr) {
                    neighbor = new Node(newX, newY, newG, newH, curr);
                    nodes[newX][newY] = neighbor;
                } else {
                    neighbor->g = newG;
                    neighbor->h = newH;
                    neighbor->parent = curr;
                }
                
                if (hasForcedNeighbor(grid, newX, newY, dx[i], dy[i])) {
                    openList.push(neighbor);  // 强制相邻节点
                } else {
                    openList.push(new Node(newX, newY, newG, newH, curr));  // 正常相邻节点
                }
            }
        }
    }
    
    // 清除节点内存
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (nodes[i][j] != nullptr) {
                delete nodes[i][j];
            }
        }
    }
    
    return path;
}

int main() {
    vector<vector<int>> grid = {
        {0, 0, 0, 0, 0},
        {0, 1, 1, 0, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 0, 0, 0}
    };
    
    int startX = 0;
    int startY = 0;
    int endX = 4;
    int endY = 4;
    
    vector<pair<int, int>> path = jps(grid, startX, startY, endX, endY);
    
    // 输出路径
    for (int i = path.size() - 1; i >= 0; i--) {
        cout << "(" << path[i].first << ", " << path[i].second << ")";
        if (i != 0) {
            cout << " -> ";
        }
    }
    cout << endl;
    
    return 0;
}

以上就是c jps优化的完整代码。使用该代码可以在给定的网格中找到起点和终点间的最短路径，并输出路径的坐标。