Given a squared chess board, find the minimum number of steps taken by a Knight

Question

Given a squared chess board, find the minimum number of steps taken by a Knight to reach desired destination from its given source...

Given a squared chess board, find the minimum number of steps taken by a Knight to reach desired destination from its given source position. As illustrated in the right figure, Knight can move to 8 different locations by a single step For instance, we need at least 3 steps to move the Knight at (2,4) to the goal position (6,1). Specifically, the Knight can move the following path: (2,4) (3,2) (4,0) (6,1). Note that, locations are represented by (vertical, horizontal) coordinates and 7 left-upper corner is (0,0) similar to the array in C/C++ Your program is required to get an input from "input_knights.txt" and write the result to a file "output_knight.txt" as the following example: input knight.txt output knight.txt 2 4 6 1 The first value in the input file indicates the chess board size N (5SNS 15). The second and third lines are the source and destination locations, repsectively. The output file only contains the minimum number of steps from the source to the destination. You can output "-1", if the destination is unreachable. Your program has to produce an answer within 5 seconds

Explanation / Answer

#include<iostream>

#include<queue>

#include<fstream>

using namespace std;

// N*N chess board

int N;

// Define possible moves for a knight

int possibleX[]={-2,-1,1,2,-2,-1,1,2};

int possibleY[]={-1,-2,-2,-1,1,2,2,1};

// to keep track of the places knight has checked into once

bool checked[20][20];

// Each square of chess board

class square{

public:

int x,y;

int steps;

square(){

}

square(int x,int y,int steps):x(x),y(y),steps(steps){

}

};

// Logic of the program to find the minimum number of steps

int solve(int Starting[], int ending[]){

queue<square> q;

int x,y;

// check starting position

checked[Starting[0]][Starting[1]]=true;

// insert the initial position into the queue

q.push(square(Starting[0],Starting[1],0));

square sq;

// loop until the queue is non-empty

while(!q.empty()){

sq=q.front();

q.pop();

checked[sq.x][sq.y]=true;

if(sq.x==ending[0] && sq.y==ending[1])

return sq.steps;

for(int i=0;i<8;i++){

x=sq.x+possibleX[i];

y=sq.y+possibleY[i];

if(x>=1 && x<=N && y>=1 && y<=N && !checked[x][y])

q.push(square(x,y,sq.steps+1));

}

}

}

int main(){

// open file for reading the input

fstream inputfile("input_knight.txt");

  

int start,end;

int Starting[2];

int ending[2];

if (inputfile.is_open()){

inputfile>>N;

inputfile>>start>>end;

Starting[0]=start; Starting[1]=end;

inputfile>>start>>end;

ending[0]=start; ending[1]=end;

inputfile.close();

}

// write to output file

ofstream outputfile("output_knight.txt");

outputfile<<solve(Starting, ending, N);

}

// Note: You need to have input_knight.txt to run the program.

File: input_knights.txt

8
2 4
6 1

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.