Answer to Question #223698 in C++ for Modrick

Question #223698

In this task, you need to understand two algorithms which can be helpful, the Breadth￾First Search which utilizes the Queue data structure to find the shortest path and the 

Depth-First Search which can traverse a Stack data structures. 

Hint:

Develop a data structure similar to binary trees. Using a standard 8 X 8 chessboard, show 

the knight’s movements in a game. As you may know, a knight’s basic move in chess is 

two forward steps and one sidestep. Facing in any direction and given enough turns, it 

can move from any square on the board to any other square. 

If you want to know the simplest way your knight can move from one square (or node) to 

another in a two-dimensional setup, you will first have to build a function like the one 

below.

knight plays ([0,0], [1,2]) == [[0,0], [1,2]]

knight plays ([0,0], [3,3]) == [[0,0], [1,2], [3,3]]

knight plays ([3,3], [0,0]) == [[3,3], [1,2], [0,0]]


1
Expert's answer
2021-08-05T17:52:12-0400
#include <iostream>
using namespace std;
struct cell {
    int x, y;
    int dis;
    cell() {}
    cell(int x, int y, int dis)
        : x(x), y(y), dis(dis)
    {
    }
};
 
bool isInside(int x, int y, int N)
{
    if (x >= 1 && x <= N && y >= 1 && y <= N)
        return true;
    return false;
}
 
int minStepToReachTarget(
    int knightPos[], int targetPos[],
    int N)
{
    int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };
    int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
 
    queue<cell> q;
 
    q.push(cell(knightPos[0], knightPos[1], 0));
 
    cell t;
    int x, y;
    bool visit[N + 1][N + 1];
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            visit[i][j] = false;
    visit[knightPos[0]][knightPos[1]] = true;
    while (!q.empty()) {
        t = q.front();
        q.pop();
        if (t.x == targetPos[0] && t.y == targetPos[1])
            return t.dis;
        for (int i = 0; i < 8; i++) {
            x = t.x + dx[i];
            y = t.y + dy[i];
 
           
            if (isInside(x, y, N) && !visit[x][y]) {
                visit[x][y] = true;
                q.push(cell(x, y, t.dis + 1));
            }
        }
    }
}
 
int main()
{
    int N = 30;
    int knightPos[] = { 1, 1 };
    int targetPos[] = { 30, 30 };
    cout << minStepToReachTarget(knightPos, targetPos, N);
    return 0;
}

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS