Самый дешевый путь

@redmait · Регистрация: 04.11.2023

Author24 — интернет-сервис помощи студентам

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

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

Входные данные

Вводятся два числа N
и M
— размеры таблицы 1⩽N⩽20,1⩽M⩽20
. Затем идёт N
строк по M
чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0
до 100
).

Выходные данные

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

код:

C++

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int n, m;
    cin >> n >> m;
    vector <vector <int>> t(n, vector <int>(m));
    for (int i = 0; i < n; ++i){
        for (int j =  0; j < m; ++j){
            cin >> t[i][j];
        }
    } vector <vector <int>> d(n + 1, vector <int>(m + 1, 0));
    for (int i = 1; i < d.size(); ++i){
        for (int j = 1; j < d.size(); ++j){
            if (j == 1){
                d[i][j] = max(d[i - 1][j], d[i][j - 1]) + t[i - 1][j - 1];
            } else {
                d[i][j] = min(d[i - 1][j], d[i][j - 1]) + t[i - 1][j - 1];
            }
        } 
    } cout << d[n][m];
    return 0;
}

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

@TheCalligrapher · 09.02.2024, 09:21

Сообщение от redmait

код вроде правильный

А как он должен работать? Почему в одной ветке max, а в другой - min?

@Kuzia domovenok · 09.02.2024, 19:43

redmait, что программист хотел написать понятно, как написал - бред полнейший

Добавлено через 2 минуты
должно выбираться минимальный вес из клеток [i-1][j] и [i][j-1] но для границ матрицы, для которых элемента -1 не существует должно быть особое условие . всё.

@Tanya2007 · 09.02.2024, 20:05

redmait, немного подкорректировала ваш код.
Есть логические ошибки:
1) В строке 16 вы не учитываете размерность вложенного вектора. Надо не до d.size(), а до m + 1.
2) В строке 17 условие не j == 1, а i == 1.
А что касается памяти, то на ограничениях входных данных вам вполне хватит типа short.

C++

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    short n, m;
    cin >> n >> m;
    vector <vector <short>> t(n, vector <short>(m));
    for (int i = 0; i < n; ++i)
    {
        for (int j =  0; j < m; ++j)
        {
            cin >> t[i][j];
        }
    }
    vector <vector <short>> d(n + 1, vector <short>(m + 1, 0));
    for (int i = 1; i < n + 1; ++i)
    {
        for (int j = 1; j < m + 1; ++j)
        {
            if (i == 1)
            {
                d[i][j] = max(d[i - 1][j], d[i][j - 1]) + t[i - 1][j - 1];
            }
            else
            {
                d[i][j] = min(d[i - 1][j], d[i][j - 1]) + t[i - 1][j - 1];
            }
        }
    }
    cout << d[n][m];
    return 0;
}

Проверьте пройдет ли по памяти?

@Kuzia domovenok · 09.02.2024, 21:06

Tanya2007, и чё поменялось?

@alexu_007 · 09.02.2024, 21:19

А как из этого кода получить путь, по которому нужно следовать для получения минимальной цены?

@TheCalligrapher · 09.02.2024, 21:26

Сообщение от alexu_007

А как из этого кода получить путь, по которому нужно следовать для получения минимальной цены?

А в чем проблема? Если у нас сохранилась исходная матрица t, то по ней и по матрице частичных решений d не составит никакого труда восстановить обратный путь от конца к началу.

Другое дело, что мне все равно не ясно, что творится в "этом коде".

@Tanya2007 · 09.02.2024, 22:09

Сообщение от TheCalligrapher

Другое дело, что мне все равно не ясно, что творится в "этом коде".

В коде специально добавлена одна нулевая строка и один нулевой столбец, как раз для того чтобы избежать головоломки для пограничный условий, когда индекс может стать -1. А чтобы не учитывать эти нули при поиске минимальной суммы пути (ведь ноль будет в любом случае меньше любой суммы), при индексах i == 1 и j == 1, берется максимум смежных ячеек, а при остальных значениях i и j - минимум.

Сообщение от Tanya2007

2) В строке 17 условие неj == 1, а i == 1.

Здесь кстати я лоханулась, условие надо проверять на i == 1 || j == 1.

@SmallEvil · 09.02.2024, 22:13

Упрощенная задача этой Найти количество способов которыми пчёлка может переместиться из клетки A в клетку B по указанным правилам
Разница лишь в том что именно мы подсчитываем.

Сообщение от Kuzia domovenok

Tanya2007, и чё поменялось?

Да ничего.

Сообщение от Kuzia domovenok

должно быть особое условие . всё.

Должно или может ?

C++

#include <iostream>
#include <vector>
using namespace std;
 
int main(){
    int n, m;
    cin >> n >> m;
    vector <vector <int>> t(n, vector <int>(m));
    for (int i = 0; i < n; ++i){
        for (int j =  0; j < m; ++j){
            cin >> t[i][j];
        }
    } 
    for (int r = 1; r < m; ++r)
        t[0][r] += t[0][r-1];
    for (int i = 1; i < n; ++i){
        t[i][0] += t[i-1][0];
        for (int j = 1; j < m; ++j)
            t[i][j] += min(t[i - 1][j], t[i][j - 1]);
    } 
 
    cout << t[n-1][m-1] << endl;
    return 0;
}

@TheCalligrapher · 09.02.2024, 22:39

Сообщение от Tanya2007

, при индексах i == 1 и j == 1, берется максимум смежных ячеек, а при остальных значениях i и j - минимум.

Другими словами, max был использован для того, чтобы не заводить две отдельные ветки: одну для i == 1, а другую - для j == 1.

Все равно сбивает с толку из-за контраста с min. Можно было

C++

1
2
3

if (i == 1 || j == 1)
  d[i][j] = d[i - 1][j] + d[i][j - 1] + t[i - 1][j - 1];
  ...

@Tanya2007 · 09.02.2024, 22:42

Сообщение от TheCalligrapher

Другими словами, max был использован для того, чтобы не заводить две отдельные ветки: одну для i == 1, а другую - для j == 1.

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

@redmait · 11.02.2024, 16:33 **[ТС]**

Спасибо, поменял тип данных на short, прошло

@SmallEvil · 11.02.2024, 17:07

Не по теме:

Сообщение от redmait

Спасибо, поменял тип данных на short, прошло

Поменял вчера старый гаджет на новый, с утроенной памятью и процом, теперь браузер грузится и ваша прога тоже :D

@redmait 0 / 0 / 0 Регистрация: 04.11.2023 Сообщений: 8
	11.02.2024, 16:33 [ТС]	12
	Спасибо, поменял тип данных на short, прошло 0

Блоги программистов
Обновление сайта www.historian.by Reglage 05.01.2025 Обещал подвести итоги 2024 года для сайта. Однако начну с того, что изменилось за неделю. Добавил краткий урок по последовательности действий при анализе вредоносных файлов и значительно улучшил урок. . .	Как использовать GraphQL в C# с HotChocolate Programming 05.01.2025 GraphQL — это современный подход к разработке API, который позволяет клиентам запрашивать только те данные, которые им необходимы. Это делает взаимодействие с API более гибким и эффективным по. . .	Модель полного двоичного суматора с помощью логических операций (python) AlexSky-coder 04.01.2025 def binSum(x:list, y:list): s=^y] p=x and y for i in range(1,len(x)): s. append((x^y)^p) p=(x and y)or(p and (x or y)) return s x=list() y=list()	Это мы не проходили, это нам не задавали...(асихронный счётчик с управляющим сигналом задержки). Hrethgir 04.01.2025 Асинхронный счётчик на сумматорах (шестиразрядный по числу диодов на плате, но наверное разрядов будет больше - восемь или шестнадцать, а диоды на старшие), так как триггеры прошли тестирование и. . .	Руководство по созданию бота для Телеграм на Python IT_Exp 04.01.2025 Боты для Телеграм представляют собой автоматизированные программы, которые выполняют различные задачи, взаимодействуя с пользователями через интерфейс мессенджера. В данной статье мы рассмотрим,. . .	Применение компонентов PrimeVue в Vue.js 3 на TypeScript BasicMan 04.01.2025 Введение в PrimeVue и настройка окружения PrimeVue представляет собой мощную библиотеку компонентов пользовательского интерфейса для Vue. js 3, которая предоставляет разработчикам богатый набор. . .
Как стать Senior developer cpp_developer 04.01.2025 В современной индустрии разработки программного обеспечения позиция Senior Developer представляет собой не просто следующую ступень карьерной лестницы, а качественно новый уровень профессионального. . .	Что известно о дате выхода Windows 12 и чего от нее ждать IT_Exp 04.01.2025 В мире технологий постоянно происходят изменения, и операционные системы не являются исключением. Windows 11, выпущенная в октябре 2021 года, принесла множество инноваций и улучшений, но. . .	Что новенького в .NET Core 9 Programming 04.01.2025 Обзор ключевых изменений в . NET Core 9 Платформа . NET Core продолжает активно развиваться, и версия 9 представляет собой значительный шаг вперед в эволюции этой технологии. Новый релиз. . .	Инструкция по установке python3.13.1 в Debian 12 AlexSky-coder 03.01.2025 sudo apt update sudo apt install build-essential zlib1g-dev libncurses5-dev libgdbm-dev libnss3-dev libssl-dev libreadline-dev libffi-dev wget. . .	Затестил триггеры. архив проекта прилагаю с GOA файлами в настройках архиватора проектов. Hrethgir 03.01.2025 В этот раз нет закольцованности, потому что от неё только глюки, как я понял, логика не вырезанная. Триггеры очень быстрые если верить измерениям с помощью анализатора от Gowin. Есть ещё регистры,. . .	Python в помощь DevOps IT_Exp 03.01.2025 Причины использования Python в работе DevOps Python стал неотъемлемой частью мира DevOps, и это не случайно. Этот язык программирования обладает множеством преимуществ, которые делают его. . .

Самый дешевый путь

Решение

Решение

@TheCalligrapher Вездепух 12798 / 6674 / 1796 Регистрация: 18.10.2014 Сообщений: 16,894
	09.02.2024, 09:21	2
	Сообщение от redmait код вроде правильный А как он должен работать? Почему в одной ветке `max`, а в другой - `min`? 0

@Kuzia domovenok 4264 / 3323 / 925 Регистрация: 25.03.2012 Сообщений: 12,520 Записей в блоге: 1
	09.02.2024, 19:43	3
	redmait, что программист хотел написать понятно, как написал - бред полнейший Добавлено через 2 минуты должно выбираться минимальный вес из клеток [i-1][j] и [i][j-1] но для границ матрицы, для которых элемента -1 не существует должно быть особое условие . всё. 0

@Kuzia domovenok 4264 / 3323 / 925 Регистрация: 25.03.2012 Сообщений: 12,520 Записей в блоге: 1
	09.02.2024, 21:06	5
	Tanya2007, и чё поменялось? 0

@alexu_007 720 / 680 / 110 Регистрация: 29.05.2015 Сообщений: 4,100
	09.02.2024, 21:19	6
	А как из этого кода получить путь, по которому нужно следовать для получения минимальной цены? 0

@TheCalligrapher Вездепух 12798 / 6674 / 1796 Регистрация: 18.10.2014 Сообщений: 16,894
	09.02.2024, 21:26	7
	Сообщение от alexu_007 А как из этого кода получить путь, по которому нужно следовать для получения минимальной цены? А в чем проблема? Если у нас сохранилась исходная матрица `t`, то по ней и по матрице частичных решений `d` не составит никакого труда восстановить обратный путь от конца к началу. Другое дело, что мне все равно не ясно, что творится в "этом коде". 0

@Tanya2007 419 / 206 / 64 Регистрация: 13.05.2020 Сообщений: 385
	09.02.2024, 22:09	8
	Сообщение от TheCalligrapher Другое дело, что мне все равно не ясно, что творится в "этом коде". В коде специально добавлена одна нулевая строка и один нулевой столбец, как раз для того чтобы избежать головоломки для пограничный условий, когда индекс может стать -1. А чтобы не учитывать эти нули при поиске минимальной суммы пути (ведь ноль будет в любом случае меньше любой суммы), при индексах `i == 1 и j == 1`, берется максимум смежных ячеек, а при остальных значениях `i и j` - минимум. Сообщение от Tanya2007 2) В строке 17 условие не`j == 1, а i == 1`. Здесь кстати я лоханулась, условие надо проверять на `i == 1 \|\| j == 1`. 1

@Tanya2007 419 / 206 / 64 Регистрация: 13.05.2020 Сообщений: 385
	09.02.2024, 22:42	11
	Сообщение от TheCalligrapher Другими словами, max был использован для того, чтобы не заводить две отдельные ветки: одну для i == 1, а другую - для j == 1. Вероятно такой была задумка ТС, насколько я понимаю. 0

@SmallEvil
	11.02.2024, 17:07 Самый дешевый путь #13
	Не по теме: Сообщение от redmait Спасибо, поменял тип данных на short, прошло Поменял вчера старый гаджет на новый, с утроенной памятью и процом, теперь браузер грузится и ваша прога тоже :D 0