knight moves: How to print the path

Hello Everyone:

I am working on the knight moves problem and managed to print the number of moves but still need to print the path e.g. "3 moves: path is: [3,3] [4,5] [2,4] [4,3]". I tried to print the Queue but got instead all visited paths so i gave up. any help is very well appreciated.
Best,
James.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384`` ``````#include #include #include 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 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(); // if current cell is equal to target cell, // return its distance if (t.x == targetPos[0] && t.y == targetPos[1]) 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; q.push(cell(x, y, t.dis + 1)); } } } } int main(){ int N = 8; int knightPos[] = { 3, 3 }; int targetPos[] = { 4, 3 }; cout << minStepToReachTarget(knightPos, targetPos, N); return 0; }``````
Last edited on
Well, for your visit[][] array you can store a previous-point array previous[][] and then when (if?) you reach your target you can just work backward through the previous points.

But are you sure that your method is guaranteed to (a) reach the target at all; (b) provide the minimum number of moves if it did so?
Thank you for the help. will try to follow your approach .
Topic archived. No new replies allowed.