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

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

Runtime error. Сan anyone say what's wrong, please?!
Послано Valera 28 окт 2019 00:29
#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

double min(double a, double b) {
    return a < b ? a : b;
}

double getWay(int **quarters, int cols, int rows) {

    double **a = new double*[cols + 1];
    for (int i = 1; i <= cols; i++)
        a[i] = new double[rows];
    for (int i = 1; i <= cols; i++) {
        for (int j = 1; j <= rows; j++)
            a[i][j] = 0;
    }

    int length = 100;
    a[1][1] = quarters[1][1] ? length * sqrt(2.0) : 2 * length;

    bool isCuted = quarters[1][1];
    for (int i = 2; i <= rows; i++) {
        if (!isCuted) {
            a[1][i] = a[1][i - 1] + length;
            if (i < rows)
                isCuted = quarters[1][i + 1];
        }
        else
            a[1][i] = (i - 1) * length + length * sqrt(2.0);
    }
    isCuted = quarters[1][1];
    for (int i = 2; i <= cols; i++) {
        if (!isCuted) {
            a[i][1] = a[i - 1][1] + length;
            if (i < cols)
                isCuted = quarters[i + 1][1];
        }
        else
            a[i][1] = (i - 1) * length + length * sqrt(2.0);
    }

    int cols_ = 2;
    int rows_ = 2;
    while (!a[cols][rows]) {

        if (cols_ <= cols) {
            for (int i = 2; i <= rows; i++) {
                double A = a[cols_][i - 1] + length;
                double B = a[cols_ - 1][i] + length;
                double C;
                if (quarters[cols_][i])
                    C = a[cols_ - 1][i - 1] + length * sqrt(2.0);
                else
                    C = a[cols_ - 1][i - 1] + length * 2;
                a[cols_][i] = min(min(A, B), C);
            }
            cols_++;
        }

        if (rows_ <= rows) {
            for (int i = 2; i <= cols; i++) {
                double A = a[i - 1][rows_] + length;
                double B = a[i][rows_ - 1] + length;
                double C;
                if (quarters[i][rows_])
                    C = a[i - 1][rows_ - 1] + length * sqrt(2.0);
                else
                    C = a[cols_ - 1][i - 1] + length * 2;
                a[i][rows_] = min(min(A, B), C);
            }
            rows_++;
        }
    }

    return a[cols][rows];
}

int main() {

    int cols, rows, k;
    cin >> cols >> rows >> k;

    int **quarters = new int*[cols + 1];
    for (int i = 1; i <= cols; i++)
        quarters[i] = new int[rows];

    for (int i = 1; i <= cols; i++) {
        for (int j = 1; j <= rows; j++)
            quarters[i][j] = 0;
    }

    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        quarters[x][y] = 1;
    }

    if (k)
        cout << round(getWay(quarters, cols, rows));
    else
        cout << (cols + rows) * 100;

    cout << endl;

    return 0;
}