C++

Forum

 
knight moves: How to print the path

jaymann (4)
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.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
#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();

        // 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
lastchance (6980)
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?
jaymann (4)
Thank you for the help. will try to follow your approach .
Topic archived. No new replies allowed.