Q:

There is a chessboard of size N×M and starting position (sx, sy) and destination position (dx,dy). You have to find out how many minimum numbers of moves a knight goes to that destination position?

0

Knight walk problem

There is a chessboard of size N×M and starting position (sx, sy) and destination position (dx,dy). You have to find out how many minimum numbers of moves a knight goes to that destination position?

Example:

Input:

knight walk

Check the above example...

If the source position is (5,5) and the destination position is (3,2).
Then the path count is 3.

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

To solve this problem we follow this approach:

  1. We use queue data structure and initialize it with the starting position and a map data structure to count the steps where the key is position and value is step count.
  2. Then we pop the top position and push all the possible positions that are reached from that position (a knight moves 2 steps at any direction and then one step left or right) and increase the step count of the popped position by one.
  3. We repeat step 2 until we reach the destination position and the first value is the minimum value.

C++ Implementation for Knight walk problem

#include <bits/stdc++.h>
using namespace std;

int num_x[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int num_y[] = { -1, 1, 2, 2, 1, -1, -2, -2 };

bool isvalid(int r, int c, int row, int col)
{
    return (row >= 0 && row < r && col >= 0 && col < c);
}

int count(int r, int c, int sx, int sy, int dx, int dy)
{
    queue<pair<pair<int, int>, int> > q;
    set<pair<int, int> > st;
    q.push(make_pair(make_pair(sx, sy), 0));
    while (!q.empty()) {
        pair<pair<int, int>, int> p = q.front();
        st.insert(make_pair(sx, sy));
        if (p.first.first == dx && p.first.second == dy) {
            return p.second;
        }
        q.pop();
        for (int i = 0; i < 8; i++) {
            int row = p.first.first + num_x[i];
            int col = p.first.second + num_y[i];
            if (isvalid(r, c, row, col) && st.find(make_pair(row, col)) == st.end()) {
                st.insert(make_pair(row, col));
                int temp = p.second + 1;
                q.push(make_pair(make_pair(row, col), temp));
            }
        }
    }
    return -1;
}

int main()
{
    int r, c;
    cout << "Row: ";
    cin >> r;
    cout << "Col: ";
    cin >> c;
    int sx, sy, dx, dy;
    cout << "Staring position : ";
    cin >> sx >> sy;
    cout << "Destination position : ";
    cin >> dx >> dy;
    cout << "Steps :";
    cout << count(r, c, sx - 1, sy - 1, dx - 1, dy - 1) << endl;
    return 0;
}

Output

Row: 5
Col: 5
Staring position : 5 5
Destination position : 3 2
Steps :3

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now