Пройти из элемента матрицы (1, 1) в (n, m) минимизируя штраф

@welcome to me · Регистрация: 11.09.2022

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

Задана матрица A натуральных чисел размера n × m. За каждый проход через элемент (i, j) взимается штраф ai, j. Необходимо минимизировать штраф и пройти из элемента (1, 1) в (n, m), при этом из текущего элемента можно перейти в любой из трёх соседних, стоящих в строке с номером, на 1 большим (т.е. из элемента (i, j) можно перейти в один из элементов (i, j − 1), (i, j), (i, j + 1), если таковые существуют).

Формат входных данных
Первая строка содержит два числа: n и m, где n — число строк матрицы A, а m — число столбцов матрицы A.
Следующие n строк задают саму матрицу A: каждая строка содержит по m целых чисел, разделённых одиночными пробелами.

Ограничения: 2 ≤ n ≤ 200, 1 ≤ m ≤ 1 000, 0 ≤ ai, j ≤ 1 000 000.

Формат выходных данных
Выведите одно целое число — минимальную стоимость пути или −1 (минус единицу), если пути нет.

Пример:
input.tx:
6 3
112 213 1
123 1 123
1 324 343
1 546 644
978 1 999
123 123 1
output.txt:
117

input.txt:
2 3
1 1 1
1 1 1
output.txt:
-1

может у кого будут идеи кода

@lemegeton · 19.10.2022, 02:36

Сообщение от welcome to me

из текущего элемента можно перейти в любой из трёх соседних, стоящих в строке с номером, на 1 большим

Это условие говорит, что двигаемся всегда на следующую строку.
Видимо дальше в скобочках опечатка:

Сообщение от welcome to me

(т.е. из элемента (i, j) можно перейти в один из элементов (i, j − 1), (i, j), (i, j + 1), если таковые существуют)

И имеется в виду, что из (i, j) можно перейти в [(i+1, j-1), (i+1, j), (i+1, j+1)].

Сообщение от welcome to me

может у кого будут идеи кода

Первое, что бросается в глаза, если m>n то пути нет.
Если m == n, то путь один -- по диагонали.
Если m < n, то использовать волновой алгоритм для поиска кратчайшего пути.

Новые блоги и статьи
Элементы алгоритмизации hw_wired 28.01.2025 Основы алгоритмизации В современном мире алгоритмы играют фундаментальную роль в развитии информационных технологий и программирования. Понимание основ алгоритмизации является ключевым элементом в. . .	Человек и информация hw_wired 28.01.2025 Введение: роль информации в познании мира В современном мире информация играет фундаментальную роль в процессе познания окружающей действительности. Она представляет собой совокупность сведений об. . .	Компьютер и информация hw_wired 28.01.2025 Эволюция вычислительных машин История развития вычислительной техники начинается задолго до появления первых электронных устройств. Человечество всегда стремилось упростить процесс вычислений и. . .	Информационные технологии hw_wired 28.01.2025 Введение в современные технологии работы с информацией В современном мире информационные технологии стали неотъемлемой частью практически всех сфер человеческой деятельности. Они существенно. . .	Информация вокруг нас hw_wired 28.01.2025 Основные понятия информации В современном мире понятие информации является фундаментальным и охватывает практически все сферы человеческой деятельности. Информация представляет собой совокупность. . .	Компьютер для начинающих hw_wired 28.01.2025 Введение в мир компьютерных технологий В современном мире информация стала одним из важнейших ресурсов человечества, определяющим развитие общества и технологий. Наша жизнь неразрывно связана с. . .
[golang] 189. Rotate Array alhaos 28.01.2025 Повороты рукоятки, целочисленный слайс нужно сдвинуть на целое положительное число. Мне очень нравится решение на GO / / https:/ / leetcode. com/ studyplan/ top-interview-150/ package topInterview . . .	КуМир: решение задач на матрицы bytestream 28.01.2025 КуМир представляет собой среду для обучения программированию, которая включает в себя мощные инструменты для работы с матрицами. Матрица в программировании - это двумерный массив, состоящий из. . .	КуМир: решение задач на строки bytestream 28.01.2025 В системе программирования КуМир работа со строковыми данными является одним из важнейших аспектов создания программ. Строки представляют собой последовательности символов, заключенные в кавычки,. . .	КуМир: решение геометрических задач bytestream 28.01.2025 Программирование геометрических задач в среде КуМир становится всё более актуальным в обучении школьников и студентов. КуМир — это разработанная в России обучающая программная среда, предназначенная. . .	КуМир, исполнитель Водолей: Задачи и решения bytestream 28.01.2025 КуМир — это образовательная среда для обучения программированию. Она предлагает пользователям разнообразные инструменты для разработки и отладки программ, что особенно ценно для студентов и. . .	КуМир, исполнитель Чертежник: Решение задач bytestream 28.01.2025 КуМир (Комплект Учебных МИРов) представляет собой образовательную среду для обучения основам программирования и алгоритмизации. Исполнитель Чертежник работает на координатной плоскости, где может. . .

@welcome to me 1 / 1 / 0 Регистрация: 11.09.2022 Сообщений: 53
		1
	Пройти из элемента матрицы (1, 1) в (n, m) минимизируя штраф 18.10.2022, 23:04. Показов 602. Ответов 1 Метки #c++, #дп (Все метки) Задана матрица A натуральных чисел размера n × m. За каждый проход через элемент (i, j) взимается штраф ai, j. Необходимо минимизировать штраф и пройти из элемента (1, 1) в (n, m), при этом из текущего элемента можно перейти в любой из трёх соседних, стоящих в строке с номером, на 1 большим (т.е. из элемента (i, j) можно перейти в один из элементов (i, j − 1), (i, j), (i, j + 1), если таковые существуют). Формат входных данных Первая строка содержит два числа: n и m, где n — число строк матрицы A, а m — число столбцов матрицы A. Следующие n строк задают саму матрицу A: каждая строка содержит по m целых чисел, разделённых одиночными пробелами. Ограничения: 2 ≤ n ≤ 200, 1 ≤ m ≤ 1 000, 0 ≤ ai, j ≤ 1 000 000. Формат выходных данных Выведите одно целое число — минимальную стоимость пути или −1 (минус единицу), если пути нет. Пример: input.tx: 6 3 112 213 1 123 1 123 1 324 343 1 546 644 978 1 999 123 123 1 output.txt: 117 input.txt: 2 3 1 1 1 1 1 1 output.txt: -1 может у кого будут идеи кода 0

@lemegeton 4866 / 2664 / 914 Регистрация: 29.11.2010 Сообщений: 5,747
	19.10.2022, 02:36	2
	Сообщение от welcome to me из текущего элемента можно перейти в любой из трёх соседних, стоящих в строке с номером, на 1 большим Это условие говорит, что двигаемся всегда на следующую строку. Видимо дальше в скобочках опечатка: Сообщение от welcome to me (т.е. из элемента (i, j) можно перейти в один из элементов (i, j − 1), (i, j), (i, j + 1), если таковые существуют) И имеется в виду, что из (i, j) можно перейти в [(i+1, j-1), (i+1, j), (i+1, j+1)]. Сообщение от welcome to me может у кого будут идеи кода Первое, что бросается в глаза, если m>n то пути нет. Если m == n, то путь один -- по диагонали. Если m < n, то использовать волновой алгоритм для поиска кратчайшего пути. 1