Input and Output for the algorithm

general
1

Hi

Help please write Input and Output for the algorithm

Algorithm:

#include <iostream>
#include <set>
#include <queue>
#include <climits>
using namespace std;

#define N 8

// Below arrays details all 8 possible movements 
// for a knight
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };

// Check if (x, y) is valid chess board coordinates
// Note that a knight cannot go out of the chessboard
bool valid(int x, int y)
{
    if (x < 0 || y < 0 || x >= N || y >= N)
        return false;

    return true;
}

// queue node used in BFS
struct Node
{
    // (x, y) represents chess board coordinates
    // dist represent its minimum distance from the source
    int x, y, dist;

    // Node constructor
    Node(int x, int y, int dist = 0): x(x), y(y), dist(dist) {}

    // As we are using struct as a key in a std::set, 
    // we need to overload < operator
    // Alternatively we can use std::pair<int, int> as a key
    // to store coordinates of the matrix in the set

    bool operator<(const Node& o) const
    {
        return x < o.x || (x == o.x && y < o.y);
    }
};

// Find minimum number of steps taken by the knight 
// from source to reach destination using BFS
int BFS(Node src, Node dest)
{
    // set to check if matrix cell is visited before or not
    set<Node> visited;

    // create a queue and enqueue first node
    queue<Node> q;
    q.push(src);

    // run till queue is not empty
    while (!q.empty())
    {
        // pop front node from queue and process it
        Node node = q.front();
        q.pop();

        int x = node.x;
        int y = node.y;
        int dist = node.dist;

        // if destination is reached, return distance
        if (x == dest.x && y == dest.y)
            return dist;

        // Skip if location is visited before
        if (!visited.count(node))
        {
            // mark current node as visited
            visited.insert(node);

            // check for all 8 possible movements for a knight
            // and enqueue each valid movement into the queue
            for (int i = 0; i < 8; ++i) 
            {
                // Get the new valid position of Knight from current
                // position on chessboard and enqueue it in the 
                // queue with +1 distance
                int x1 = x + row[i];
                int y1 = y + col[i];

                if (valid(x1, y1))
                    q.push({x1, y1, dist + 1});
            }
        }
    }

    // return INFINITY if path is not possible
    return INT_MAX;
}

// main function
int main()
{
    // source coordinates
    Node src = {0, 7};

    // destination coordinates
    Node dest = {7, 0};

    cout << "Minimum number of steps required is " << BFS(src, dest);

    return 0;
}

This is what should be in Input and Output:

from the console we enter how many examples there will be and how many chess horses are on the board, and their starting points (that is, where they are), and the points to which the horses must go in the least number of steps.

  • 2 - number of examples
  • 1 - the number of chess knights
  • 5 5 - the starting point
  • 5 6 - the final point
  • 2 - the number of chess knights
  • 0 0 - the starting point of the first knight
  • 1 0 - the starting point of the second knight
  • 0 1 - the final point of the first knight
  • 1 1 - the final point of the second knight

Answer:

  • 3 - the answer for the first example
  • 4 - the answer for the second example

Please help, I will be very grateful !!!

2

please