C++ 链表实现路径查找算法优化：使用 DFS 提升代码效率

#include #include

using namespace std;

struct node { int x, y; node *next; };

bool include(node n, int x, int y) { node *p = &n; while (p != nullptr) { if (p->x == x && p->y == y) return true; p = p->next; } return false; }

bool validPosition(int n, int m, node pos, int adjX, int adjY) { return pos.x + adjX >= 0 && pos.x + adjX < n && pos.y + adjY >= 0 && pos.y + adjY < m; }

void appendNode(node *&front, int adjX, int adjY) { node *temp = new node; temp->x = front->x + adjX; temp->y = front->y + adjY; temp->next = nullptr; front->next = temp; front = temp; }

int num(int n, int m, int x1, int y1, int x2, int y2) { int ans = 0; node temp = {x1, y1}, *head = &temp, *front, *x, *old; old = front = head; do { cout << front->x << ' ' << front->y << endl; if (front->x == x2 && front->y == y2)ans++; else { x = head; while (x->next && x->next->next && x->next->next->next)x = x->next; if (validPosition(n, m, *front, 1, 0) && !include(*old, front->x + 1, front->y + 0)) appendNode(front, 1, 0); if (validPosition(n, m, *front, 1, 1) && !include(*old, front->x + 1, front->y + 1)) appendNode(front, 1, 1); if (validPosition(n, m, *front, 0, 1) && !include(*old, front->x + 0, front->y + 1)) appendNode(front, 0, 1); if (validPosition(n, m, *front, -1, 1) && !include(*old, front->x - 1, front->y + 1)) appendNode(front, -1, 1); if (validPosition(n, m, *front, -1, 0) && !include(*old, front->x - 1, front->y + 0)) appendNode(front, -1, 0); if (validPosition(n, m, *front, -1, -1) && !include(*old, front->x + 1, front->y - 1)) appendNode(front, -1, -1); if (validPosition(n, m, *front, 0, -1) && !include(*old, front->x + 0, front->y - 1)) appendNode(front, 0, -1); if (validPosition(n, m, *front, 1, -1) && !include(*old, front->x + 1, front->y - 1)) appendNode(front, 1, -1); x->next = x->next->next; x = head; while (x)x = x->next; front = x; } } while (front != head); return ans; }

int main() { cout << num(4, 4, 1, 1, 3, 3); return 0; }

这段代码的问题在于，它使用了一个指针变量node *p来遍历链表，但是在include函数中，node n是一个局部变量，它会在函数结束时销毁，而p指向的是n的地址，所以在include函数返回后，p将不再是有效的指针。因此，我们需要将链表定义为动态内存分配的节点，并使用new操作符来创建新的节点。

另外，代码中的num函数实现了一个寻找从(x1, y1)到(x2, y2)的路径的算法，但是它的实现方式不太直观。我们可以考虑使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决这个问题，而不是使用链表来存储路径。

以下是使用DFS来求解的示例代码：

#include <iostream>
#include <vector>

using namespace std;

bool validPosition(int n, int m, int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

void dfs(int n, int m, int x, int y, int targetX, int targetY, int& count) {
    if (x == targetX && y == targetY) {
        count++;
        return;
    }
    
    static int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
    static int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
    
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (validPosition(n, m, nx, ny)) {
            dfs(n, m, nx, ny, targetX, targetY, count);
        }
    }
}

int num(int n, int m, int x1, int y1, int x2, int y2) {
    int count = 0;
    dfs(n, m, x1, y1, x2, y2, count);
    return count;
}

int main() {
    cout << num(4, 4, 1, 1, 3, 3);
    return 0;
}

这段代码使用了深度优先搜索（DFS）来遍历所有可能的路径，当搜索到达目标位置时，计数器count加1。最终返回的count即为从起点到终点的路径数量。