VBNet - Форум - Кладотолкатель

Вопрос: Кладотолкатель Добавлено: 06.01.06 17:17

Автор вопроса: ASiD | ICQ: 259132473

Задача 5. "Кладотолкатель" (50 баллов)
Лабиринт представляет собой матрицу MxN, некоторые ячейки которой пустые, а остальные заполнены камнями. В одной из пустых ячеек находится клад, а в другой — кладотолкатель. Кладотолкатель и клад не могут находиться в ячейках, заполненных камнями, за пределами лабиринта, а также одновременно в одной и той же ячейке. Кладотолкатель может передвигаться в соседнюю ячейку (соседними считаются ячейки, граничащие по стороне), а также передвигать клад следующим образом: нужно встать в соседнюю к кладу ячейку и толкнуть его от себя. При этом клад передвинется в соседнюю ячейку в направлении, заданном толчком, а кладотолкатель переместится в ячейку, где только что находился клад.
Требуется написать программу, которая определяет последовательность толчков и передвижений кладотолкателя, следуя которой клад можно передвинуть к выходу (выход находится в пустой ячейке). Так как клад очень тяжелый, количество толчков должно быть минимальным. При наличии нескольких оптимальных последовательностей следует указать любую из них.
Технические требования:
Имя входного файла: Input.txt
Имя выходного файла: Output.txt
Ограничение по времени тестирования: 2 секунды на один тест на Intel Celeron 2500.
Формат входных данных:
Первая строка входного файла содержит числа М и N . Следующие М строк содержат описание лабиринта. Каждая строка состоит из N символов, описывающих ячейки лабиринта: заполненная камнями ячейка обозначается латинской буквой 'X', пустая ячейка обозначается символом '.' (ASCII код 46), начальная позиция кладотолкателя — буквой 'Y', начальная позиция клада — латинской буквой 'В', выход — латинской буквой 'Т'.
Формат выходных данных:
Если решения не существует, то файл должен cодержать слово 'NO'. Иначе, в первой строке выходного файла должно содержаться слово 'YES', а во второй строке — последовательность символов, определяющая действия кладотолкателя, в частности, символы 'w', 'e', 'n', 's' обозначают передвижения кладотолкателя на запад, восток, север и юг соответственно, а символы 'W', 'E', 'N', 'S' обозначают толчки кладотолкателя в соответствующих направлениях.

Input.txt
3 3
..Y
.B.
TXX

Output.txt
YES
sWnwS
Ответить

Ответы Всего ответов: 8

Номер ответа: 1 Автор ответа: Sergey ICQ: 283551900 Вопросов: 1 Ответов: 74	Профиль \| \| #1	Добавлено: 06.01.06 21:17
	Задачу нужно разделить на две части. 1) Найти ячейки, на которые можно двигать клад. Пример в угол двигать нельзя!! К стенки двигать тоже нельзя если невозможно потом клад отодвинуть от стенки (исключение если по стенки клад двигается к выходу). 2) На найденном поле (состоит из найденных ячеек) найти минимальный путь от клада к выходу и двигать его по этому пути. Еще одон вариант. Строишь орграф. Каждое поле это вершина. Если можешь придвинуть из вершина ‘а’ в соседнею вершину ‘b’ клад за один толчок то из ‘а’ есть ребро в ‘b’ длиной(весом) 1. На орграфе находишь минимальный путь от клада к выходу и двигать его по этому пути. Ответить

Номер ответа: 2 Автор ответа: Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979	Web-сайт: sharpc.livejournal.com Профиль \| \| #2	Добавлено: 06.01.06 23:35
	Думаю, проще решить через динамическое программирование - для каждой ячейки пишем список, за сколько и какие ходы ее можно достигнуть. Ход считается возможным, если от позиции, на которой стоял ящик перед предыдущим сдвигом достижима клетка, с которой надо толкнуть ящик, волновым алгоритмом. Ответить

Номер ответа: 3 Автор ответа: Sergey ICQ: 283551900 Вопросов: 1 Ответов: 74	Профиль \| \| #3	Добавлено: 07.01.06 00:09
	Думаю, проще решить через динамическое программирование - для каждой ячейки пишем список, за сколько и какие ходы ее можно достигнуть. Ход считается возможным, если от позиции, на которой стоял ящик перед предыдущим сдвигом достижима клетка, с которой надо толкнуть ящик, волновым алгоритмом. Тоже самое только по-другому написано. какие ходы ее можно достигнуть. Ход считается возможным, если от позиции, на которой стоял ящик перед предыдущим сдвигом достижима клетка, с которой надо толкнуть ящик, волновым алгоритмом.[/ = Если можешь придвинуть из вершина ‘а’ в соседнею вершину ‘b’ клад за один толчок то из ‘а’ есть ребро в ‘b’ длиной(весом) 1. для каждой ячейки пишем список, за сколько... На орграфе находишь минимальный путь от клада к выходу Ответить

Номер ответа: 4 Автор ответа: Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979	Web-сайт: sharpc.livejournal.com Профиль \| \| #4	Добавлено: 07.01.06 02:29
	Ты не указал, как строить орограф Ответить

Номер ответа: 5 Автор ответа: ASiD ICQ: 259132473 Вопросов: 19 Ответов: 23	Профиль \| \| #5	Добавлено: 07.01.06 13:32
	Спасибо! Ответить

Номер ответа: 6 Автор ответа: Wolfrt ICQ: 225421504 Вопросов: 8 Ответов: 60	Профиль \| \| #6	Добавлено: 08.01.06 16:09
	Нюансов много. Наверняк массив будет значительный. найти путь от клада до выхода. при условии чтокладоискатель может дойти до точек. т.е. оббежать препятсвия) далее рекурсивным методом определяем путь с наименьшем количеством толчков! а орограф что такое? Ответить

Номер ответа: 7 Автор ответа: Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979	Web-сайт: sharpc.livejournal.com Профиль \| \| #7	Добавлено: 08.01.06 16:51
	Рекурсия тут возможна только в сочетании с динамическим программированием, т.к. дерево очень часто ветвится, а глубина никак не меньше длины правильного пути. Орограф - это искаженное название орграфа - ориентированного графа. Ответить

Номер ответа: 8 Автор ответа: Wolfrt ICQ: 225421504 Вопросов: 8 Ответов: 60	Профиль \| \| #8	Добавлено: 08.01.06 18:42
	Всё понял! Графы вспомнил! Самое главно всё предусмотреть! Подобная задача: Дан массив NxN заполненный числами, найти путь из точки 1,1 в точку N,M с наименьшей суммой. я Её решил но на мой взгляд коряво! Если есть граммотное решение с использованием "Орограф" выложите пожалуйста. Ответить

Страница: 1 |