ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1119. Метро

С++ Acc
Послано matvey22122 15 май 2020 19:23
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <vector>
#include <string>
#include <regex>
#include <cmath>
#include <set>
#include <map>

using namespace std;

struct Coordinata
{
    int x;
    int y;
};


struct addedCoordinata
{
    int x;
    int y;
    double length;
};
vector<addedCoordinata> addC;

vector<Coordinata> getPoints (int x, int y, const vector<Coordinata>& array) {
    vector<Coordinata> arr;
    for (auto dot : array) {
        if (dot.x <= x && dot.y <= y) {
            arr.push_back(dot);
        }
    }
    return arr;
};

double checkAdded (int x, int y) {
    for (auto point : addC) {
        if (point.x == x && point.y == y) return point.length;
    }
    return -1;
}

double solve(int n, int m, const vector<Coordinata>& array) {

    double check = checkAdded(n, m);
    if (check != -1) return check;

    double res = 99999999;
    for (auto point : getPoints(n, m, array)) {
        double distance = solve(point.x-1, point.y-1, array) + sqrt(20000.0) + (n - point.x + m - point.y) * 100;
        if (distance < res) res = distance;
    }
    if (res == 99999999) {
        addedCoordinata koor;
        koor.x = n;
        koor.y = m;
        koor.length = (n + m) * 100;
        addC.push_back(koor);
        return koor.length;
    };

    addedCoordinata koor;
    koor.x = n;
    koor.y = m;
    koor.length = res;
    addC.push_back(koor);

    return res;
}


int main() {
    ios::sync_with_stdio(false);

    int n, m , k;
    vector<Coordinata> array;
    cin >> n >> m >> k;
    for (int i = 0; i < k; ++i) {
        int x, y;
        cin >> x >> y;
        Coordinata xy{};
        xy.x = x;
        xy.y = y;
        array.push_back(xy);
    }

    cout.setf(ios::fixed,ios::floatfield);
    cout.precision(0);

    cout << solve(n, m, array);

    return 0;
}