• API
• FAQ
• Tools
• Archive
SHARE
TWEET

LAB 7 not correct

Mary_99 Jan 30th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. // storing a cell's data
6. struct cell
7. {
8.     int x, y;
9.     int dis;
10.     cell() {}
11.     cell(int x, int y, int dis) : x(x), y(y), dis(dis) {}
12. };
13.
14. //  returns true if (x, y) lies
15. // inside Board
16. bool is_inside(int x, int y, int N)
17. {
18.     if (x >= 1 && x <= N && y >= 1 && y <= N)
19.         return true;
20.     return false;
21. }
22.
23. // returns minimum step to reach target position
24. int min_step_to_reach_target(int knight_pos[], int target_pos[],int N)
25. {
26.     // knight direction
27.     int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
28.     int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};
29.
30.     //  storing states of knight in board
31.     queue<cell> q;
32.
33.     // push starting position of knight with 0 distance
34.     q.push(cell(knight_pos[0], knight_pos[1], 0));
35.
36.     cell t;
37.     int x, y;
38.     bool visit[N + 1][N + 1];
39.
40.     //cell unvisited
41.     for (int i = 1; i <= N; i++)
42.         for (int j = 1; j <= N; j++)
43.             visit[i][j] = false;
44.
45.     // visit starting state
46.     visit[knight_pos[0]][knight_pos[1]] = true;
47.
48.     // until one element in queue
49.     while (!q.empty())
50.     {
51.         t = q.front();
52.         q.pop();
53.
54.         // if current cell = target cell,
55.         // return its distance
56.         if (t.x == target_pos[0] && t.y == target_pos[1])
57.             return t.dis;
58.
59.         // all reachable states
60.         for (int i = 0; i < 8; i++)
61.         {
62.             x = t.x + dx[i];
63.             y = t.y + dy[i];
64.
65.             // If reachable state is not yet visited and
66.             // inside board, push that state into queue
67.             if (is_inside(x, y, N) && !visit[x][y]) {
68.                 visit[x][y] = true;
69.                 q.push(cell(x, y, t.dis + 1));
70.             }
71.         }
72.     }
73. }
74.
75. // test above methods
76. int main()
77. {
78.     int N = 8;
79.     int knight_pos[] = {2, 2};
80.     int target_pos[] = {8, 8};
81.     cout << min_step_to_reach_target(knight_pos, target_pos, N);
82.     return 0;
83. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?