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

@appleforms · Регистрация: 30.01.2020

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

Прямоугольный остров разделён на квадраты, так что его размеры – 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

@mr-Crocodile · 11.02.2020, 11:29

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

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

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

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

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

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

	Напишите программу, которая находит наибольшее количество монет, которое может собрать пират, и выводит его маршрут 10.02.2020, 20:51. Показов 1763. Ответов 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

@mr-Crocodile 3053 / 1672 / 657 Регистрация: 19.03.2019 Сообщений: 5,381
	11.02.2020, 11:29
	appleforms, это классическая задача для ДП (ДП - это динамическое программирование). гугли "черепашка динамическое программирование" суть решения через ДП в том, что создавай массив размером N+1, M+1 и заполняй его максимальным значением, которое можно получить в данной клетке двигаясь с разных направлений. как дойдёшь до конечной клетки, готово. наибольшее значение сразу готово (это и есть значение в конечной точке) и теперь выбирай из матрицы путь, который даёт максимум. Добавлено через 8 минут вдогонку. и тут на форуме черепашка была Задача про черепашку. Динамическое программирование https://www.cyberforum.ru/post6573276.html 0