Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- // storing a cell's data
- struct cell
- {
- int x, y;
- int dis;
- cell() {}
- cell(int x, int y, int dis) : x(x), y(y), dis(dis) {}
- };
- // returns true if (x, y) lies
- // inside Board
- bool is_inside(int x, int y, int N)
- {
- if (x >= 1 && x <= N && y >= 1 && y <= N)
- return true;
- return false;
- }
- // returns minimum step to reach target position
- int min_step_to_reach_target(int knight_pos[], int target_pos[],int N)
- {
- // knight direction
- int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
- int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};
- // storing states of knight in board
- queue<cell> q;
- // push starting position of knight with 0 distance
- q.push(cell(knight_pos[0], knight_pos[1], 0));
- cell t;
- int x, y;
- bool visit[N + 1][N + 1];
- //cell unvisited
- for (int i = 1; i <= N; i++)
- for (int j = 1; j <= N; j++)
- visit[i][j] = false;
- // visit starting state
- visit[knight_pos[0]][knight_pos[1]] = true;
- // until one element in queue
- while (!q.empty())
- {
- t = q.front();
- q.pop();
- // if current cell = target cell,
- // return its distance
- if (t.x == target_pos[0] && t.y == target_pos[1])
- return t.dis;
- // all reachable states
- for (int i = 0; i < 8; i++)
- {
- x = t.x + dx[i];
- y = t.y + dy[i];
- // If reachable state is not yet visited and
- // inside board, push that state into queue
- if (is_inside(x, y, N) && !visit[x][y]) {
- visit[x][y] = true;
- q.push(cell(x, y, t.dis + 1));
- }
- }
- }
- }
- // test above methods
- int main()
- {
- int N = 8;
- int knight_pos[] = {2, 2};
- int target_pos[] = {8, 8};
- cout << min_step_to_reach_target(knight_pos, target_pos, N);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement