Complete the Given program of traversing a knight in a chess board from a start

Question

 Complete the Given program of traversing a knight in a chess board from a start point to end point using depth first search(DFS) and breadth first search(BFS). Cannot edit class pos(int move(int k) can be edited) and int main    #include <iostream> #include <vector> #include <queue> #include <stack>  using namespace std;  class pos { public:         int id;//0...63         bool visited;         bool in_wait;         int from_id;         pos() { id = -1; visited = false; in_wait = false; from_id = -1; }         int move(int k) {                 //For this move direction (1 ... 8)                 //return the new_id once a move is made                 //or any illeagal value not in 0...63          } };  void print_path(vector<pos> &board, int k); void data_input(int &start_id, int &end_id); void BFS(vector<pos> &board, int &start_id, int &end_id); void DFS(vector<pos> &board, int &start_id, int &end_id);  //You are not allowed to modify main or class pos. //For class pos, you need to implement move functiion //will explain this in class. int main() {         vector<pos> board(64);         for (int i = 0; i < 64; i++) board[i].id = i;         //queue<int> Queue;         int start_id = -1, end_id = -1; //legal values are 0 ... 63         data_input(start_id, end_id);         BFS(board, start_id, end_id);         for (int i = 0; i < 64; i++) {                 board[i].id = i;                 board[i].visited = false;                 board[i].in_wait = false;                 board[i].from_id = -1;         }         DFS(board, start_id, end_id);          getchar();         getchar();         return 0; }  void data_input(int &start_id, int &end_id) {         //stard_id, end_id will be in 0 ... 63  }  void BFS(vector<pos> &board, int &start_id, int &end_id) {    // Your code here.         //If you find no solution, print the following         //cout << "No solution is possible" << endl; }   void DFS(vector<pos> &board, int &start_id, int &end_id) {         // Your code here.    //If you find no solution, print the following    //cout << "No solution is possible" << endl; }   void print_path(vector<pos> &board, int k) {         //In both DFS and BFS, when the target postion is reached, this function will be called.          //Your code }   //The following is a sample screenshot.  You have to ensure that your output format is idential to it.  /* Enter starting position --  x is in a ... h and y is in 1 ... 8 b 3 Enter ending position -- x is in a ... h and y is in 1 ... 8 f 2  Target is reached! (f,2) <-- (e,4) <-- (d,2) <-- (b,3)  Target is reached! (f,2) <-- (d,1) <-- (c,3) <-- (a,2) <-- (b,4) <-- (a,6) <-- (c,7) <-- (a,8) <-- (b,6) <-- (c,4) <-- (e,5) <-- (g,6) <-- (f,8) <-- (h,7) <-- (f,6) <-- (g,8) <-- (h,6) <-- (f,5) <-- (d,4) <-- (b,3) 

Explanation / Answer

#include <bits/stdc++.h>
using namespace std;
struct cell
{
int a, b;
int dist;
cell() {}
cell(int a, int b, int dist) : a(a), b(b), dist(dist) {}
};
bool isInside(int a, int b, int N)
{
if (a >= 1 && a <= N && b >= 1 && b <= N)
return true;
return false;
}
int minStepToReachTarget(int knight_pos[], int target_pos[],
int N)
{
int d_x[] = {-2, -1, 1, 2, -2, -1, 1, 2};
int d_y[] = {-1, -2, -2, -1, 1, 2, 2, 1};
queue<cell> q;
q.push(cell(knight_pos[0], knight_pos[1], 0));
cell t;
int a, b;
bool visits[N + 1][N + 1];
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
visits[i][j] = false;
visits[knight_pos[0]][knight_pos[1]] = true;
while (!q.empty())
{
t = q.front();
q.pop();
if (t.a == target_pos[0] && t.b == target_pos[1])
return t.dist;
for (int i = 0; i < 8; i++)
{
a = t.a + d_x[i];
b = t.b + d_y[i];
if (isInside(a, b, N) && !visits[a][b]) {
visits[a][b] = true;
q.push(cell(a, b, t.dist + 1));
}
}
}
}
int main()
{
int N = 30;
int knight_pos[] = {1, 1};
int target_pos[] = {30, 30};
cout << minStepToReachTarget(knight_pos, target_pos, N);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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