C++ 计算从一个点到另一个点的路径数量 - 优化代码示例

#include\x3ciostream\x3e\n#include\x3calgorithm\x3e\n\nusing namespace std;\n\nstruct node {\n int x, y;\n node next;\n};\n\nbool include(node n, int x, int y) {\n node* p = n;\n while (p != nullptr) {\n if (p->x == x && p->y == y) return true;\n p = p->next;\n }\n return false;\n}\n\nbool validPosition(int n, int m, node* pos, int adjX, int adjY) {\n return pos->x + adjX >= 0 && pos->x + adjX < n && pos->y + adjY >= 0 && pos->y + adjY < m;\n}\n\nvoid appendNode(node*& front, int adjX, int adjY) {\n node* temp = new node;\n temp->x = front->x + adjX;\n temp->y = front->y + adjY;\n temp->next = nullptr;\n front->next = temp;\n front = temp;\n}\n\nint num(int n, int m, int x1, int y1, int x2, int y2) {\n int ans = 0;\n node* temp = new node {x1, y1, nullptr};\n node* head = temp;\n node* front = head;\n node* old = front;\n int count = 0;\n do {\n cout << front->x << " " << front->y << endl;\n if (front->x == x2 && front->y == y2) ans++;\n else {\n node* x = head;\n while (x->next && x->next->next && x->next->next->next) x = x->next;\n if (validPosition(n, m, front, 1, 0) && !include(old, front->x + 1, front->y + 0))\n appendNode(front, 1, 0);\n if (validPosition(n, m, front, 1, 1) && !include(old, front->x + 1, front->y + 1))\n appendNode(front, 1, 1);\n if (validPosition(n, m, front, 0, 1) && !include(old, front->x + 0, front->y + 1))\n appendNode(front, 0, 1);\n if (validPosition(n, m, front, -1, 1) && !include(old, front->x - 1, front->y + 1))\n appendNode(front, -1, 1);\n if (validPosition(n, m, front, -1, 0) && !include(old, front->x - 1, front->y + 0))\n appendNode(front, -1, 0);\n if (validPosition(n, m, front, -1, -1) && !include(old, front->x + 1, front->y - 1))\n appendNode(front, -1, -1);\n if (validPosition(n, m, front, 0, -1) && !include(old, front->x + 0, front->y - 1))\n appendNode(front, 0, -1);\n if (validPosition(n, m, front, 1, -1) && !include(old, front->x + 1, front->y - 1))\n appendNode(front, 1, -1);\n x->next = x->next->next;\n front = head;\n while (front->next) front = front->next;\n }\n count++;\n if (count > n * m) break;\n } while (front != head);\n while (head) {\n node* temp = head;\n head = head->next;\n delete temp;\n }\n return ans;\n}\n\nint main() {\n cout << num(4, 4, 1, 1, 3, 3);\n return 0;\n}\n\n\n#include\x3ciostream\x3e\n#include\x3calgorithm\x3e\n\nusing namespace std;\n\nbool validPosition(int n, int m, int x, int y) {\n return x >= 0 && x < n && y >= 0 && y < m;\n}\n\nint num(int n, int m, int x1, int y1, int x2, int y2) {\n if (x1 == x2 && y1 == y2) return 1;\n int ans = 0;\n if (validPosition(n, m, x1 + 1, y1 + 0)) ans += num(n, m, x1 + 1, y1 + 0, x2, y2);\n if (validPosition(n, m, x1 + 1, y1 + 1)) ans += num(n, m, x1 + 1, y1 + 1, x2, y2);\n if (validPosition(n, m, x1 + 0, y1 + 1)) ans += num(n, m, x1 + 0, y1 + 1, x2, y2);\n if (validPosition(n, m, x1 - 1, y1 + 1)) ans += num(n, m, x1 - 1, y1 + 1, x2, y2);\n if (validPosition(n, m, x1 - 1, y1 + 0)) ans += num(n, m, x1 - 1, y1 + 0, x2, y2);\n if (validPosition(n, m, x1 - 1, y1 - 1)) ans += num(n, m, x1 - 1, y1 - 1, x2, y2);\n if (validPosition(n, m, x1 + 0, y1 - 1)) ans += num(n, m, x1 + 0, y1 - 1, x2, y2);\n if (validPosition(n, m, x1 + 1, y1 - 1)) ans += num(n, m, x1 + 1, y1 - 1, x2, y2);\n return ans;\n}\n\nint main() {\n cout << num(4, 4, 1, 1, 3, 3);\n return 0;\n}