Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.85
name?
198 / 169 / 18
Регистрация: 01.06.2010
Сообщений: 371
Завершенные тесты: 1
#1

Задача "Сокобан" - C++

26.07.2013, 15:59. Просмотров 1750. Ответов 9
Метки нет (Все метки)

Ограничение времени: 5.0 секунды
Ограничение памяти: 64 МБ
Программист Стас на время отпуска устроился поработать в японскую компьютерную фирму Thinking Rabbit. Сначала идея казалась замечательной — и на халяву съездить за границу, и заработать, и набраться опыта у японских коллег. Но оказалось, что программисты без знания японского фирме не нужны, и Стаса отправили работать кем-то вроде кладовщика (по-японски его профессию называли Soko-ban).
Стас должен наводить порядок на складе, точнее, расставлять контейнеры с грузом по местам. Каждое утро Стасу дают бумажку со схемой очередного помещения и указанием, куда надо поставить контейнеры (почему-то начальству фирмы Thinking Rabbit не важно, какой именно контейнер куда поставить, главное, чтобы все контейнеры стояли только на отмеченных местах).
Однако, расставить их не так просто. Контейнеры большие и тяжелые, так что передвигать их можно, только толкая по полу, причем сил хватает лишь на один контейнер за раз. Кстати, контейнеры еще и гладкие, поэтому их можно толкать перед собой, но невозможно, например, тянуть за собой или поворачивать. Габариты помещения точно подогнаны под размеры контейнеров, поэтому Стас не может перебраться через контейнер, протиснуться между стоящими рядом контейнерами или пролезть между контейнером и стеной — он может ходить только по свободному пространству. Поэтому наведение порядка превращается в жуткую головоломку. А если решить её не удается или контейнер случайно попадает в какой-нибудь угол, из которого его не вытащить, то Стасу не позавидуешь. Дело в том, что стены склада сплошные, без выходов. Утром Стас попадает на склад через один из люков в потолке, а выйти из помещения он может только тогда, когда выполнит свою задачу. Умная система управления откроет люк для Стаса в нужном месте.
Помогите Стасу составить план перемещения контейнеров.
Исходные данные
На входе задана схема склада — прямоугольная сетка размером n × m (3 ≤ n, m ≤ 8). Пустое место обозначется пробелом, а объекты обозначаются следующими символами:
# — стены
. — пустое место, куда нужно поставить контейнер (цель)
@ — место, откуда начинает работу Стас
+ — место, откуда начинает работу Стас, если там находится одна из целей
$ — контейнер на пустом месте
* — контейнер на одной из целей
Гарантируется, что схема склада задана корректно, т.е. Стас не может выйти за его пределы. Количество контейнеров совпадает с количеством целей.
Результат
Выведите строку, описывающую план перемещений Стаса, при котором он расставляет контейнеры по конечным позициям. Все перемещения записываются буквами r, l, u и d (соответствующие четырем направлениям перемещений). Если при перемещении двигается контейнер, то буквы записываются в верхнем регистре (R, L, U и D соответственно). Длина строки не должна превышать 10000 символов. Можете считать, что решение всегда существует.
Примеры
HTML5
1
2
3
4
5
6
7
8
9
10
11
12
исходные данные результат
########
#@  $ .#                rrRR
########
 
 ######
##   .#
#@  ###              dddrrrruLdlUUUluRR
#   * #
#   $ #
#     #
#######
по идее чтоб решить эту задачу нужно знать волновой алгоритм(хотя думаю с ним просто по времени не впищемся) и все делать пошагово. У кого-то есть еще какие-то идеи как ее решать?)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.07.2013, 15:59     Задача "Сокобан"
Посмотрите здесь:

Страуструп, "Принципы и практика использования С++": задача на нахождение моды - C++
Здравствуйте ,решаю упражнения из книги "Страуструп принципы и практика использования c++", столкнулся с модой (4 глава 16 упражнение) при...

Вычислить значение суммы. Задача с использованием "длинной арифметики". - C++
Тема: «Задачи на длинную арифметику» Задача: Вычислить точное значение суммы 1^2 + 2^2 + 3^2 + ... + n^2 (n ≥ 20000). Пожалуйста,...

Задача "Кто старше?" (подскажите где ошибка в коде) - C++
Здравствуйте!подскажите где может быть ошибка, на сайте показывает частичное решение, Условие: Программа принимает три числа: возраст...

Задача решена только нужна "нитра" фишки по ускорению - C++
Задача такая, создать файл заданного размера к примеру 500 мегабайтов, в него на генерировать рандомно данные а потом их отсортировать в...

Задача "Гигабашня": минимальное расстояние до этажа со счастливым номером - C++
Гигабашня — самое высокое и глубокое здание в Киберленде. В ней 17 777 777 777 этажей, пронумерованных от  - 8 888 888 888 до...

Найти ошибку в решении "Числа - палиндрома" (задача с acmp) - C++
У меня WA на 4-ом тесте. #include <stdio.h> #include <stdio.h> #include <math.h> #include <cstdio> #include <algorithm> ...

Перевод из двоичной системы в десятичную, задача 2.30 "Как программировать на С++" - C++
Здравствуйте! Не могу решить задачу из книги. Задача Введите целые данные, содержащие только нули и единицы (т.е. «двоичные»...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Wolkodav
601 / 454 / 32
Регистрация: 18.09.2012
Сообщений: 1,685
26.07.2013, 16:09     Задача "Сокобан" #2
Есть такой алгоритм A*, почитай, может поможет как-нибудь.

Добавлено через 2 минуты
Хотя его еще придётся модернизировать как-нибудь...
name?
198 / 169 / 18
Регистрация: 01.06.2010
Сообщений: 371
Завершенные тесты: 1
26.07.2013, 16:12  [ТС]     Задача "Сокобан" #3
Цитата Сообщение от Wolkodav Посмотреть сообщение
Есть такой алгоритм A*, почитай, может поможет как-нибудь.

Добавлено через 2 минуты
Хотя его еще придётся модернизировать как-нибудь...
это и есть волновой алгоритм, тут скорее всего нужно использовать Алгоритм поиска пути Jump Point Search.
интересно вообще кто-то из форума пытался ее решить?
З.Ы. задача висит в топе сложнейших на acm.timus.ru
Evg
Эксперт CАвтор FAQ
17470 / 5708 / 363
Регистрация: 30.03.2009
Сообщений: 15,670
Записей в блоге: 26
26.07.2013, 17:39     Задача "Сокобан" #4
Цитата Сообщение от name? Посмотреть сообщение
интересно вообще кто-то из форума пытался ее решить?
Бугога...
Несколько небольших игрушек

Цитата Сообщение от Evg Посмотреть сообщение
Кстати, поищи коллекцию под названием "yoshio autogenerated". Там такие же маленькие уровни, но с тремя камнями. Они поинтереснее. В своё время я очень конкретно засел на одном уровне, аж написал программу, которая решение ищет
Могу продать, если найду

Добавлено через 2 минуты
Правда у меня было решение методом перебора (но такие маленькие уровни решались быстро). При этом глубину перебора нужно было задавать параметром. Т.е. если задача решаема за 10 ходов, а задано ограничение в 20 ходов, то программа найдёт решение, которое не более 20 ходов, и решение будет НЕ кратчайшим
Dani
1278 / 636 / 56
Регистрация: 11.08.2011
Сообщений: 2,277
Записей в блоге: 2
Завершенные тесты: 1
26.07.2013, 17:52     Задача "Сокобан" #5
Evg, если бы можно сделать перебором, то эта задача не висела бы в топе сложнейших. Для поля 8*8 можно соорудить решение больше чем за 10 ходов, которые уже не отпереборит твоя программа. И тут, увы, TLE
Evg
Эксперт CАвтор FAQ
17470 / 5708 / 363
Регистрация: 30.03.2009
Сообщений: 15,670
Записей в блоге: 26
26.07.2013, 18:00     Задача "Сокобан" #6
Я и не говорю, что у меня идеальная программа и решает всё. Мне нужно было разрулить уровень 8 на 8, который мозгами я пройти не смог. Написал программу, она нашла решение, после чего я успокоился
name?
198 / 169 / 18
Регистрация: 01.06.2010
Сообщений: 371
Завершенные тесты: 1
26.07.2013, 18:50  [ТС]     Задача "Сокобан" #7
Цитата Сообщение от Evg Посмотреть сообщение
Бугога...
Несколько небольших игрушек

Добавлено через 2 минуты
дык написать игрушку не проблема, а вот вот оптимальный ИИ для ее прохождения...

Цитата Сообщение от Evg Посмотреть сообщение
Могу продать, если найду

Добавлено через 2 минуты
Правда у меня было решение методом перебора (но такие маленькие уровни решались быстро). При этом глубину перебора нужно было задавать параметром. Т.е. если задача решаема за 10 ходов, а задано ограничение в 20 ходов, то программа найдёт решение, которое не более 20 ходов, и решение будет НЕ кратчайшим
Продавать не нужно) если найдешь, то проверь пройдет ли все тесты на АСМ твоя программа
Evg
Эксперт CАвтор FAQ
17470 / 5708 / 363
Регистрация: 30.03.2009
Сообщений: 15,670
Записей в блоге: 26
26.07.2013, 19:43     Задача "Сокобан" #8
Цитата Сообщение от name? Посмотреть сообщение
Продавать не нужно
"Могу продать" - это собирательное выражение Не думаю, что кто-то согласится такую лажу купить

Цитата Сообщение от name? Посмотреть сообщение
то проверь пройдет ли все тесты на АСМ твоя программа
Это что такое?
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,922
Записей в блоге: 1
26.07.2013, 20:08     Задача "Сокобан" #9
Цитата Сообщение от name? Посмотреть сообщение
З.Ы. задача висит в топе сложнейших на acm.timus.ru
какой смысл переписывать задачи с одного сайта на другой? Кто заинтересуется этой проблемой пойдёт на acm.timus.ru и решит её там!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.07.2013, 23:46     Задача "Сокобан"
Еще ссылки по теме:

Задача "Гонки по улицам" (обход ориентированного графа) - C++
Здравствуйте,помогите с задачей,если можно с комметарием,чтобы разобраться.Спасибо На рисунке ниже изображен пример плана улиц для гонки....

Структуры... Задача: "База сотрудников небольшой фирмы" - C++
По каждому сотруднику вводится следующая информация: • Фамилия, имя, отчество; • год и дата рождения; • пол; • стаж работы по...

Задача из книги "Програмирование - принципы и практика использования C++" - C++
Кто читал ету книгу, помогите разобратся с задачей с 12 главы. Никак не могу скомпилировать простую программу. Вот ее код: #include...

Задача "Максимальный подпалиндром" не могу поймать ошибку. - C++
Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется...

Задача "Движение по клеткам таблицы" (Динамическое программирование) - C++
Хотел узнать, может у кого-нибудь в архивах есть подобная задача, которую можно будет использовать как шаблон к моей. Есть таблица NxM,...


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

Или воспользуйтесь поиском по форуму:
Evg
Эксперт CАвтор FAQ
17470 / 5708 / 363
Регистрация: 30.03.2009
Сообщений: 15,670
Записей в блоге: 26
26.07.2013, 23:46     Задача "Сокобан" #10
Блин... я что-то подумал, что "АСМ" - это ассемблер...
Yandex
Объявления
26.07.2013, 23:46     Задача "Сокобан"
Ответ Создать тему
Опции темы

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