我正在研究骑士移动问题，并设法打印移动数量，但仍然需要打印路径，例如"3移动:路径是:[3,3][4,5][2,4][4,3]"。我试图打印队列，但得到的却是所有访问过的路径。我也试着向后工作到前面的点(函数minStepToReachTarget)，但我认为我的新手技能没有帮助。我已经知道了移动的次数，但是否有一个函数或一段代码可以帮助我打印路径?
最好的,詹姆斯。
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
using namespace std;
// structure for storing a cell's data
class cell {
public:
int x, y;
int dis;
cell() {}
cell(int x, int y, int dis) : x(x), y(y), dis(dis) { }
};
// Utility method returns true if (x, y) lies
// inside Board
bool isInside(int x, int y, int N)
{
if (x >= 1 && x <= N && y >= 1 && y <= N)
return true;
return false;
}
// Method returns minimum step
// to reach target position
int minStepToReachTarget( int knightPos[], int targetPos[], int N)
{
// x and y direction, where a knight can move
int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };
int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
// queue for storing states of knight in board
queue<cell> q;
// push starting position of knight with 0 distance
q.push(cell(knightPos[0], knightPos[1], 0));
cell t;
int x, y;
bool visit[N + 1][N + 1];
// make all cell unvisited
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
visit[i][j] = false;
// visit starting state
visit[knightPos[0]][knightPos[1]] = true;
// loop until we have one element in queue
while (!q.empty()) {
t = q.front();
q.pop();
// cout << "[" << t.x << " "<< t.y<<"]n";
// if current cell is equal to target cell,
// return its distance
if (t.x == targetPos[0] && t.y == targetPos[1]) {
// cout << "[" << targetPos[0] << " " << targetPos[1] << "]n";
return t.dis;
}
// loop for all reachable states
for (int i = 0; i < 8; i++) {
x = t.x + dx[i];
y = t.y + dy[i];
// If reachable state is not yet visited and
// inside board, push that state into queue
if (isInside(x, y, N) && !visit[x][y]) {
visit[x][y] = true;
//** cout << "[" << x << " " << y << "]n";
q.push(cell(x, y, t.dis + 1));
}
}
}
return t.dis;
}
int main(){
int N = 8, knightPos[2], targetPos[2];
cout <<"=> Enter the current Knight’s location: ";
for (int i = 0; i < 2; i++) std::cin>> knightPos[i];
cout <<"=> Enter the destination location: ";
for (int i = 0; i < 2; i++) std::cin>> targetPos[i];
cout <<"=> You made it in " << minStepToReachTarget(knightPos, targetPos, N) <<
" moves from [" << knightPos[0] <<"," << knightPos[1] << "] "
"to [" << targetPos[0] <<"," << targetPos[1] <<"]! Here is your path: ";
return 0;
/*
=> Enter the current Knight’s location: 3 3
=> Enter the destination location: 4 3
=> You made it in 3 moves from [3,3] to [4,3]! Here is your path:
[3,3] [4,5] [2,4] [4,3]
*/
}
您正在对您的板进行广度优先搜索。一旦到达目的地，函数minStepToReachTarget不知道它是如何到达那里的。你能做的是，对于队列中的每个单元，跟踪它的"父单元"，即从哪个单元首先访问它。找到目标后，您可以跟踪t的父节点，而不是返回t.dis，并返回一个表示路径的数组。t.dis将等于数组的长度减去1，因为您在路径中同时包含了起点和目标点。