@appleforms

Прямоугольный остров разделён на квадраты, так что его размеры – N на M квадратов. В каждом квадрате с координатами ( i , j ) (сначала указывается строка, потом – столбец) зарыто Z ij золотых монет. Карта расположена так, что север соответствует направлению вверх. Ячейки в строках и столбцах нумеруются с единицы, левый верхний угол имеет координаты (1, 1) .

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

Входные данные
В первой строке вводятся два натуральных числа: N и M ( 2 ≤ N , M ≤ 1000 ), разделённые пробелом. В каждой из следующих N строк записаны через пробел по M чисел, которые обозначают количество монет, зарытых в каждом квадрате острова (квадраты перечисляются по строкам с севера на юг, в каждой строке – с запада на восток).

Выходные данные
В первой строке программа должна вывести наибольшее количество монет, которое может собрать пират. Во второй строке без пробелов выводятся шаги, которые нужно выполнить пирату: буква 'E' (от слова east ) обозначает шаг на восток, а буква 'N' (от слова north ) – шаг на север.

Примеры
входные данные
3 3
1 2 3
2 5 7
1 3 2
выходные данные
19
ENEN

0

@mr-Crocodile

appleforms, это классическая задача для ДП (ДП - это динамическое программирование).
гугли "черепашка динамическое программирование"

суть решения через ДП в том, что создавай массив размером N+1, M+1 и заполняй его максимальным значением, которое можно получить в данной клетке двигаясь с разных направлений. как дойдёшь до конечной клетки, готово. наибольшее значение сразу готово (это и есть значение в конечной точке) и теперь выбирай из матрицы путь, который даёт максимум.

Добавлено через 8 минут
вдогонку.
и тут на форуме черепашка была

Задача про черепашку. Динамическое программирование

https://www.cyberforum.ru/post6573276.html

0