Пройти из элемента матрицы (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, то использовать волновой алгоритм для поиска кратчайшего пути.

@welcome to me 1 / 1 / 0 Регистрация: 11.09.2022 Сообщений: 53
		1
	Пройти из элемента матрицы (1, 1) в (n, m) минимизируя штраф 18.10.2022, 23:04. Показов 588. Ответов 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 4863 / 2662 / 913 Регистрация: 29.11.2010 Сообщений: 5,743
	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