|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
19.12.2022, 15:56 | #1 |
Новичок
Джуниор
Регистрация: 19.12.2022
Сообщений: 4
|
Задача:Только вправо или вниз С++
Игровое поле N×M заполняется целыми числами, одно неотрицательное целое число в каждой клетке. Цель игры состоит в том, чтобы пройти по любому разрешенному пути от верхнего левого угла до правого нижнего. Целое число в каждой клетке указывает, какой длины шаг должен быть из текущей клетки. Все шаги могут быть или направо или вниз. Если в результате какого-либо шага игрок покидает пределы поля, такой шаг запрещается.
Требуется написать программу, которая определит число различных вариантов путей от верхнего левого угла до правого нижнего (и их отображения). Результаты располагать в порядке увеличения шагов. А также найти такой путь из клетки старта в клетку финиша, чтобы сумма цифр в клетках, через которые он пролегает, была минимальной. Входные данные: размеры поля N (1 ≤ N ≤ 70) и M (1 ≤ M ≤ 70). N строк, каждая из которых описывает отдельную строку игрового поля, записанные через пробел по M целых чисел - длины шагов из клеток данной строки. |
19.12.2022, 16:11 | #2 |
Форумчанин
Регистрация: 27.04.2022
Сообщений: 494
|
Длина шага (цифра в клетке) чем-то ограничена?
В правый нижний угол я так понимаю вход без разницы какой лины шаг?
стимулятор https://yoomoney.ru/to/41001303250491
Последний раз редактировалось Valick; 19.12.2022 в 16:15. |
19.12.2022, 16:17 | #3 |
Новичок
Джуниор
Регистрация: 19.12.2022
Сообщений: 4
|
Длина шага не ограничена.
В правый нижний угол я так понимаю вход без разницы какой длины шаг? да без разницы. |
19.12.2022, 16:31 | #4 |
Форумчанин
Регистрация: 27.04.2022
Сообщений: 494
|
Так не интересно, я бы всё таки ограниил шаг в клетке рандомным числом от 1 до минимального из (N, M)
Например игровое поле 10х15, значит шаги от 1 до 10. А то как-то записывать в клетку число с 30-тью нулями при размере поля 10 на 10 "не айс".
стимулятор https://yoomoney.ru/to/41001303250491
|
19.12.2022, 16:43 | #5 |
Новичок
Джуниор
Регистрация: 19.12.2022
Сообщений: 4
|
В задаче четко про это не написано, поэтому я думаю можно и ограничить. Единственное шаг (число в клетке) может быть и 0. В примере вот такое поле изображено.
|
19.12.2022, 17:31 | #6 |
Форумчанин
Регистрация: 27.04.2022
Сообщений: 494
|
Blugu, ок. задача интересная, люблю такие. К сожалению очень мало свободного времени, но первое что приходит в голову. Это берём координату 0.0 с числом 2 (шаг 1) и проверяем шаг вправо (шаг 2) и шаг вниз (шаг 3), если оба шага доступны, то сохраняем эти шаги с информацией о том откуда сделан шаг (т.е. коордтната 0.0), повторяем этот алгоритм для каждого их сохранённых шагов, если же ход недоступен, то просто не сохраняем эту ветку. В итоге собираем в цепочки только те шаги которые достигли конца (от конца к началу).
стимулятор https://yoomoney.ru/to/41001303250491
|
20.12.2022, 06:49 | #7 |
Новичок
Джуниор
Регистрация: 19.12.2022
Сообщений: 4
|
Поиск все возможных путей
Найти и вывести количество все возможных путей в матрице, от верхнего левого угла до правого нижнего, двигаться можно только вправо или вниз.
|
20.12.2022, 08:06 | #8 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,341
|
Объединил темы, т.к. обсуждается практически одна и та же задача. Хотя количество путей и сами пути, это разные вещи. Прототип на питоне, который считает количество путей:
Код:
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Как мне спустить страницу вниз в нужные место, только медленна | ОльгаЯ | JavaScript, Ajax | 2 | 02.12.2013 11:55 |
Осуществить циклический сдвиг элементов прямоугольной матрицы на n элементов вправо или вниз | Nekro95 | Помощь студентам | 12 | 07.11.2012 22:31 |
задача на си только поскорее | zorra123 | Общие вопросы C/C++ | 4 | 30.04.2012 10:06 |
Заполнение матрицы по спирали (от центра влево-вниз-вправо-вверх) | Баур | Помощь студентам | 4 | 03.12.2009 17:39 |