Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <set>
- using namespace std;
- struct Point{
- const int x;
- const int y;
- bool operator < (const Point& other)const{
- if (x != other.x){
- return x < other.x;
- }
- return y < other.y;
- }
- };
- class Field{
- public:
- explicit Field(int width, int height): distances_(height+1, vector<int>(width+1, -1)), width_(width), height_(height){}
- int calculate_sum_distance(Point& start){
- queue<Point> q;
- distances_[start.y][start.x] = 0;
- q.push(start);
- bfs(q);
- int result = 0;
- for (const auto& target : targets_){
- if (distances_[target.y][target.x] == -1){
- return -1;
- } else{
- result += distances_[target.y][target.x];
- }
- }
- return result;
- };
- void add_target(const Point& p){
- targets_.push_back(p);
- }
- private:
- void bfs(queue<Point>& q){
- Point v = q.front();
- q.pop();
- for (const auto& neighbour : get_neighbours(v)){
- if(distances_[neighbour.y][neighbour.x] == -1){
- distances_[neighbour.y][neighbour.x] = distances_[v.y][v.x]+1;
- q.push(neighbour);
- }else{
- if (distances_[v.y][v.x] + 1 < distances_[neighbour.y][neighbour.x]){
- distances_[neighbour.y][neighbour.x] = distances_[v.y][v.x] + 1;
- }
- }
- }
- if (!q.empty()){
- bfs(q);
- }
- }
- set<Point> get_neighbours(Point& v) const{
- set<Point> result;
- result.insert({v.x+1, v.y+2});
- result.insert({v.x+1, v.y-2});
- result.insert({v.x-1, v.y-2});
- result.insert({v.x-1, v.y+2});
- result.insert({v.x+2, v.y-1});
- result.insert({v.x+2, v.y+1});
- result.insert({v.x-2, v.y-1});
- result.insert({v.x-2, v.y+1});
- auto result_copy = result;
- for (auto n : result_copy){
- if (n.x < 1 || n.x > width_ || n.y < 1 || n.y > height_){
- result.erase(n);
- }
- }
- return result;
- }
- int height_;
- int width_;
- vector<vector<int>> distances_;
- vector<Point> targets_;
- };
- int main(){
- int height, width, target_x, target_y, knights_amount;
- scanf("%d%d", &height, &width);
- Field field(width, height);
- scanf("%d%d", &target_x, &target_y);
- Point start{target_x, target_y};
- scanf("%d", &knights_amount);
- for (int _ = 0; _ < knights_amount; ++_){
- int x, y;
- scanf("%d%d", &x, &y);
- field.add_target({x, y});
- }
- int dist = field.calculate_sum_distance(start);
- printf("%d", dist);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement