Problem #3. (Programming) Knight (20 pts) Given a squared chess board, find the
ID: 3589132 • Letter: P
Question
Problem #3. (Programming) Knight (20 pts) 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 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 (S S N S 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. You are asked to briefly describe your algorithm in the report and name your source code file "ID_Al Knight.eppExplanation / Answer
#include <iostream>
#include <queue>
using namespace std;
// representation of a cell
struct cell
{
int xPos, yPos;
int distance;
cell() {}
cell(int xPos, int yPos, int distance) : xPos(xPos), yPos(yPos), distance(distance) {}
};
bool isInsideBoard(int xPos, int yPos, int sizeOfBoard)
{
if (xPos >= 1 && xPos <= sizeOfBoard && yPos >= 1 && yPos <= sizeOfBoard) {
return true;
}
return false;
}
int minStepRequiredToReachTarget(int currentPos[], int targetPos[],int sizeOfBoard)
{
// to update knight position
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(currentPos[0], currentPos[1], 0));
cell currentCell;
int x, y;
bool visit[sizeOfBoard + 1][sizeOfBoard + 1];
for (int i = 1; i <= sizeOfBoard; i++){
for (int j = 1; j <= sizeOfBoard; j++) {
visit[i][j] = false;
}
}
visit[currentPos[0]][currentPos[1]] = true;
while (!q.empty())
{
currentCell = q.front();
q.pop();
visit[currentCell.xPos][currentCell.yPos] = true;
//reached to targePosition
if (currentCell.xPos == targetPos[0] && currentCell.yPos == targetPos[1]) {
return currentCell.distance;
}
//loop throw all posible moves
for (int i = 0; i < 8; i++)
{
x = currentCell.xPos + dx[i];
y = currentCell.yPos + dy[i];
if (isInsideBoard(x, y, sizeOfBoard) && !visit[x][y]) {
q.push(cell(x, y, currentCell.distance + 1));
}
}
}
}
int main()
{
int sizeOfBoard ;
int currentPos[2] ;
int targetPos[2] ;
cin >> sizeOfBoard;
cin >> currentPos[0] >> currentPos[1];
cin >> targetPos[0] >> targetPos[1];
cout << minStepRequiredToReachTarget(currentPos, targetPos, sizeOfBoard);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.