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

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

C++ ACC
Послано Vlad Haivas 12 авг 2019 17:34
#include <bits/stdc++.h>

using namespace std;
double dp[1005][1005];
int diag[1005][1005];
int main()
{
    int i,n,m,q,j;
    cin >> m>> n >> q;
    while(q--){
        int x,y;
        cin >> y >> x;
        x = x  + 1;
        y = y + 1;
        diag[x][y] = 1;
    }

    for(i = 0;i <= n + 2;i++){
        for(j = 0;j <= m + 2;j++){
            dp[i][j] = 2e9;
        }
    }
    for(i = 1;i <= n + 1;i++){
        for(j = 1;j <= m + 1;j++){
            dp[i][j] = 0;
            dp[i][j] = min(100 + dp[i - 1][j],dp[i][j-1] + 100);
            if(diag[i][j]){
                dp[i][j] = min(dp[i][j],dp[i - 1][j - 1] + 100 * sqrt(2));
            }
            dp[1][1] = 0;
        }
    }
    cout << round(dp[n + 1][m + 1]);
    return 0;
}