0 / 0 / 0
Регистрация: 30.01.2020
Сообщений: 10
1

Напишите программу, которая находит наибольшее количество монет, которое может собрать пират, и выводит его маршрут

10.02.2020, 20:51. Показов 701. Ответов 1
Метки нет (Все метки)

Прямоугольный остров разделён на квадраты, так что его размеры – 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.02.2020, 20:51
Ответы с готовыми решениями:

посмотрите функцию пожалуйста
посмотрите плиз функцию ХУ, там надо вывести по десять целых значений х и у, но у меня не...

Посмотрите, пожалуйста, тест
Какое значение получит переменная d после выполнения оператора d:=odd(a)<>x в Pascal при a=true и...

Пожалуйста, посмотрите эти 2 задачи!
1.)Найти все натуральные числа, меньшие или равные N, делящиеся на любую из своих цифр. 2.)Найти...

Посмотрите пожалуйста мою программу. В чем моя ошибка?
Даны e,n массивы a(n), b(n). Вычислить S=(x+2)/(x^2+5^2)+(x+7)/(x^2+6^2)+(x+12)/(x^2+7^2)+......

1
2385 / 1174 / 479
Регистрация: 19.03.2019
Сообщений: 3,811
11.02.2020, 11:29 2
appleforms, это классическая задача для ДП (ДП - это динамическое программирование).
гугли "черепашка динамическое программирование"

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

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

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

https://www.cyberforum.ru/post6573276.html
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.02.2020, 11:29

Посмотрите пожалуйста,не могу понять,в чем завоздка,что не там...
задание на фотке(( program pr_2_3; uses crt,Linear_algebra; const WG=100; type tmatr=array of...

задачу на завтра пожалуйста

Помогите пожалуйста задачу решить (((
Дан типизированный файл, содержащий информацию о расписании поездов: номер поезда, название (откуда...

Помогите пожалуйста решить задачу!!!
Полоса стального прокта имеет сечение А*В. Можно ли из этой полосы получить призматическую деталь с...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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