Question

Your program should read from an input file, which will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

Answer 1

#include <bits/stdc++.h>

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();

visit[t.x][t.y] = true;

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])

q.push(cell(x, y, t.dis + 1));

}

}

}

int main(){

ifstream obj("input.txt");

string line;

int x1,y1,x2,y2;

while(getline(obj,line)){

//cout<<line<<endl;

x1=line[0]-'a'+1;

y1=line[1]-'0';

x2=line[3]-'a'+1;

y2=line[4]-'0';

int N = 8;

int knightPos[] = {x1,y1};

int targetPos[] = {x2,y2};

cout <<"To get from "<<line[0]<<line[1]<<" to "<<line[3]<<line[4]<<" takes "<< minStepToReachTarget(knightPos, targetPos, N)<<" Knight Moves."<<endl;

}

return 0;

}