Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Live4Sky
6 / 1 / 0
Регистрация: 04.10.2013
Сообщений: 42
1

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

06.05.2014, 05:18. Просмотров 1338. Ответов 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 Мб Сложность: 15%)
есть задача ********/?main=task&amp;id_task=148 и есть код #include &lt;fstream&gt;...

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

Сократить код ( Вырубка деревьев (Время: 1 сек. Память: 16 Мб Сложность: 46%)
всем привет решил написать код от 24-ой задачи с ******** вот код #include...

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

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

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.05.2014, 05:18

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

Сложность во время запуска
Здравствуйте. Вы моя последняя надежда и опора. В общем я решил обновить своей...

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


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

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

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