Advertisement
Mary_99

LAB 7 not correct

Jan 30th, 2019
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.94 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement