Advertisement
sacr1ficerq

fucking D

Apr 21st, 2022
33
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.80 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.         queue<Point> q;
  28.         distances_[start.y][start.x] = 0;
  29.         q.push(start);
  30.         bfs(q);
  31.         int result = 0;
  32.         for (const auto& target : targets_){
  33.             if (distances_[target.y][target.x] == -1){
  34.                 return -1;
  35.             } else{
  36.                 result += distances_[target.y][target.x];
  37.             }
  38.         }
  39.  
  40.  
  41.         return result;
  42.     };
  43.  
  44.  
  45.  
  46.     void add_target(const Point& p){
  47.         targets_.push_back(p);
  48.     }
  49.  
  50. private:
  51.     void bfs(queue<Point>& q){
  52.         Point v = q.front();
  53.         q.pop();
  54.         for (const auto& neighbour : get_neighbours(v)){
  55.             if(distances_[neighbour.y][neighbour.x] == -1){
  56.                 distances_[neighbour.y][neighbour.x] = distances_[v.y][v.x]+1;
  57.                 q.push(neighbour);
  58.             }else{
  59.                 if (distances_[v.y][v.x] + 1 < distances_[neighbour.y][neighbour.x]){
  60.                     distances_[neighbour.y][neighbour.x] = distances_[v.y][v.x] + 1;
  61.                 }
  62.             }
  63.         }
  64.         if (!q.empty()){
  65.             bfs(q);
  66.         }
  67.     }
  68.  
  69.     set<Point> get_neighbours(Point& v) const{
  70.         set<Point> result;
  71.         result.insert({v.x+1, v.y+2});
  72.         result.insert({v.x+1, v.y-2});
  73.         result.insert({v.x-1, v.y-2});
  74.         result.insert({v.x-1, v.y+2});
  75.         result.insert({v.x+2, v.y-1});
  76.         result.insert({v.x+2, v.y+1});
  77.         result.insert({v.x-2, v.y-1});
  78.         result.insert({v.x-2, v.y+1});
  79.         auto result_copy = result;
  80.         for (auto n : result_copy){
  81.             if (n.x < 1 || n.x > width_ || n.y < 1 || n.y > height_){
  82.                 result.erase(n);
  83.             }
  84.         }
  85.         return result;
  86.     }
  87.  
  88.     int height_;
  89.     int width_;
  90.  
  91.     vector<vector<int>> distances_;
  92.     vector<Point> targets_;
  93. };
  94.  
  95. int main(){
  96.     int height, width, target_x, target_y, knights_amount;
  97.  
  98.     scanf("%d%d", &height, &width);
  99.     Field field(width, height);
  100.  
  101.     scanf("%d%d", &target_x, &target_y);
  102.     Point start{target_x, target_y};
  103.  
  104.     scanf("%d", &knights_amount);
  105.  
  106.     for (int _ = 0; _ < knights_amount; ++_){
  107.         int x, y;
  108.         scanf("%d%d", &x, &y);
  109.         field.add_target({x, y});
  110.     }
  111.  
  112.     int dist = field.calculate_sum_distance(start);
  113.     printf("%d", dist);
  114.  
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement