Advertisement
sacr1ficerq

D

Apr 21st, 2022
34
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.76 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. struct Point{
  9.     const int x;
  10.     const int y;
  11.  
  12.     bool operator < (const Point& other)const{
  13.         if (x != other.x){
  14.             return x < other.x;
  15.         }
  16.         return y < other.y;
  17.     }
  18.  
  19. };
  20.  
  21.  
  22. class Field{
  23. public:
  24.     explicit Field(int width, int height): distances_(height+1, vector<int>(width+1, -1)), width_(width), height_(height){}
  25.  
  26.     int calculate_sum_distance(Point& start){
  27.         bfs(start);
  28.         int result = 0;
  29.         for (const auto& target : targets_){
  30.             if (distances_[target.y][target.x] == -1){
  31.                 return -1;
  32.             } else{
  33.                 result += distances_[target.y][target.x];
  34.             }
  35.         }
  36.  
  37.         return result;
  38.     };
  39.  
  40.     void add_target(const Point& p){
  41.         targets_.push_back(p);
  42.     }
  43.  
  44. private:
  45.  
  46.     void bfs(Point& start){
  47.         queue<Point> q;
  48.         distances_[start.y][start.x] = 0;
  49.         q.push(start);
  50.         while (!q.empty()){
  51.             auto v = q.front();
  52.             q.pop();
  53.             for (const auto& neighbour : get_neighbours(v)){
  54.                 if(distances_[neighbour.y][neighbour.x] == -1){
  55.                     distances_[neighbour.y][neighbour.x] = distances_[v.y][v.x]+1;
  56.                     q.push(neighbour);
  57.                 }
  58.                 else if(distances_[v.y][v.x] + 1 < distances_[neighbour.y][neighbour.x]){
  59.                         distances_[neighbour.y][neighbour.x] = distances_[v.y][v.x] + 1;
  60.                 }
  61.             }
  62.         }
  63.     }
  64.  
  65.     set<Point> get_neighbours(Point& v) const{
  66.         set<Point> result;
  67.         result.insert({v.x+1, v.y+2});
  68.         result.insert({v.x+1, v.y-2});
  69.         result.insert({v.x-1, v.y-2});
  70.         result.insert({v.x-1, v.y+2});
  71.         result.insert({v.x+2, v.y-1});
  72.         result.insert({v.x+2, v.y+1});
  73.         result.insert({v.x-2, v.y-1});
  74.         result.insert({v.x-2, v.y+1});
  75.         auto result_copy = result;
  76.         for (auto n : result_copy){
  77.             if (n.x < 1 || n.x > width_ || n.y < 1 || n.y > height_){
  78.                 result.erase(n);
  79.             }
  80.         }
  81.         return result;
  82.     }
  83.  
  84.     int height_;
  85.     int width_;
  86.  
  87.     vector<vector<int>> distances_;
  88.     vector<Point> targets_;
  89. };
  90.  
  91. int main(){
  92.     int height, width, target_x, target_y, knights_amount;
  93.  
  94.     cin >> height >> width;
  95.     Field field(width, height);
  96.  
  97.     cin >> target_x >> target_y;
  98.     Point start{target_x, target_y};
  99.  
  100.     cin >> knights_amount;
  101.  
  102.     for (int _ = 0; _ < knights_amount; ++_){
  103.         int x, y;
  104.         cin >> x >> y;
  105.         field.add_target({x, y});
  106.     }
  107.  
  108.     int dist = field.calculate_sum_distance(start);
  109.     cout << dist;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement