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

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

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

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

06.05.2014, 05:18. Просмотров 759. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.05.2014, 05:18     Минимальный путь в таблице (Время: 1 сек. Память: 16 Мб Сложность: 32%)
Посмотрите здесь:

C++ Время выполнения(сложность)
Задача про минимальный путь в лабиринте. C++
C++ Вывести на экран путь, пройденный пешеходом, если известны его скорость и время движения
C++ Доброго время суток. Как выбрать правильный путь?
Найти минимальный путь на земельном участке вдоль ограждения C++
НОД (Время: 1 сек. Память: 16 Мб Сложность: 15%) C++
Единицы (Время: 1 сек. Память: 16 Мб Сложность: 16%) C++
C++ Сократить код ( Вырубка деревьев (Время: 1 сек. Память: 16 Мб Сложность: 46%)
C++ Минимальный путь из левой верхней в правую нижнюю клетку таблицы.
C++ Время выполнения и затраченная память
Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину C++
Оценить время выполнения и сложность простейших операций с разными типами данных C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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