Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Live4Sky
6 / 1 / 1
Регистрация: 04.10.2013
Сообщений: 42
#1

Минимальный путь в таблице (Время: 1 сек. Память: 16 Мб Сложность: 32%) - C++

06.05.2014, 05:18. Просмотров 840. Ответов 0
Метки нет (Все метки)

Кликните здесь для просмотра всего текста

В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).

Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.
Входные данные

Во входном файле INPUT.TXT задано два числа N и M - размеры таблицы (1<=N<=20, 1<=M<=20). Затем идет N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).
Выходные данные

В выходной файл OUTPUT.TXT выведите минимальную сумму, потратив которую можно попасть в правый нижний угол.

примеры:
вход - 3 4
1 1 1 1
5 2 2 100
9 4 2 1
выход(ответ) - 8
вот есть код,в чем проблема..собственно есть 3 цикла в программе, 1 и 2 цикл я знаю, что делают,что делает 3-й цикл? в голове не укладывается,помогите
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <algorithm>
#include<fstream>
using namespace std;
int a[30][30], n, m;
int main() {
    ifstream cin("input.txt");
    ofstream cout("output.txt");
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        cin >> a[i][j];
    for (int j = 1; j < m; j++){
        a[0][j] += a[0][j - 1];
        //cout << a[0][j] << " ";// здесь будет 2 3 4
    }
    for (int i = 1; i < n; i++){
        a[i][0] += a[i - 1][0];
        //cout << a[i][0] << " ";//здесь будет 6 15
    }
    for (int i = 1; i < n; i++){
        for (int j = 1; j < m; j++){
        a[i][j] += min(a[i - 1][j], a[i][j - 1]);
        //cout << a[i][j] << endl;здесь как ?min понятно как работает
        }
    }
    cout<< a[n - 1][m - 1]<<endl;//здесь 8
    return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.05.2014, 05:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Минимальный путь в таблице (Время: 1 сек. Память: 16 Мб Сложность: 32%) (C++):

НОД (Время: 1 сек. Память: 16 Мб Сложность: 15%) - C++
есть задача ********/?main=task&amp;id_task=148 и есть код #include &lt;fstream&gt; main(){ std::fstream i( &quot;input.txt&quot; ), o( &quot;output.txt&quot;,...

Единицы (Время: 1 сек. Память: 16 Мб Сложность: 16%) - C++
задача http://********/?main=task&amp;id_task=22 с ацмп есть код #include&lt;fstream&gt; main(){ std::fstream i(&quot;input.txt&quot;),o(&quot;output.txt&quot;,...

Сократить код ( Вырубка деревьев (Время: 1 сек. Память: 16 Мб Сложность: 46%) - C++
всем привет решил написать код от 24-ой задачи с ******** вот код #include &lt;fstream&gt; int main(){ std::fstream...

Время выполнения(сложность) - C++
Как вычислить время выполнения программы? и что такое NlogN?

Минимальный путь в таблице - Free Pascal
В прямоугольной таблице N×M (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход...

Определить путь S, пройденный лодкой (путь=время*скорость). - Delphi
Скорость лодки в стоячей воде V км/ч, скорость течения реки U км/ч (U&lt;V). Время движения лодки по озеру Т1 ч, а по реке против течения Т2...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.05.2014, 05:18
Привет! Вот еще темы с ответами:

Сложность во время запуска - Компьютерное железо
Здравствуйте. Вы моя последняя надежда и опора. В общем я решил обновить своей девушке ПК, что бы она могла играть в Sims 3. Заказал много...

Ограничить время симуляции 600 сек - GPSS
Смоделировать работу системы в течение 600 сек. Я ограничил по лимиту 600 транзактов, как сделать лимит по времени, чтобы после 600-ой...

Пересчёт значения каждые 30 сек(сравнивая время) - MS Excel
Подскажите пожалуйста... -1ая ячейка(А) - значение -2ая (B) время как посчитать сумму значений в промежутке времени 30 секунд. ...

Гаснет экран на пару сек во время теста - Процессоры
Гаснет экран на 1-3 сек но комп работает и когда включается мон все работает тест продолжается, тест OCCT CPU:linpack Проц i74790k...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru