|
|
|
|
|
|
|
| 1 Дячук Антон, 15 сентября 2026 г. 16:17:15 |
| (Продолжение) Публиковать свои рекордные раскладки или раскрывать все секреты поиска не требуется — каждый делится только тем, чем готов поделиться. Со своей стороны готов описать опробованные подходы, их результаты и ограничения, а также участвовать в сравнении методов на общих нерекордных примерах. Для начала достаточно обменяться сообщениями здесь. Если найдётся несколько заинтересованных участников, можно будет договориться о небольшом отдельном чате. Есть ли здесь те, кто занимался именно построением сильных лабиринтов? Особенно интересно, какие конструктивные идеи или способы поиска помогали находить новые семейства раскладок, а не только небольшие улучшения одной исходной карты. Если обсуждение уже существует в другом месте, буду благодарен за подсказку. Антон
|
|
|
| 2 Дячук Антон, 15 сентября 2026 г. 16:16:09 |
| Поиск рекордных лабиринтов для «Жука»: обмен опытом Всем здравствуйте! По совету Сергея Беляева обращаюсь к участникам этого обсуждения. Ищу тех, кому интересна не только симуляция движения жука из задачи №399, но и обратная задача: строить лабиринты, в которых жук как можно дольше ищет выход, как в соревновании на BugLab. Я экспериментирую с программами поиска, локальными изменениями одной и нескольких клеток, рекурсивным развитием раскладок и разными способами выбора перспективных ветвей. Хотелось бы обмениваться опытом с теми, кто тоже занимался этой задачей или хотел бы попробовать. Особенно интересует переход от локального улучшения уже найденной раскладки к принципиально новым конструкциям: как выбирать исходную структуру, выходить из локальных максимумов и не тратить большую часть вычислений на почти одинаковые варианты. Предлагаю обсуждать общие идеи, алгоритмы, ускорение расчётов и результаты экспериментов, включая неудачные. Публиковать свои рекордные раскладки или раскрывать все секр
|
|
|
| 3 Дитер Никус, 14 января 2026 г. 19:29:51 |
| Решение задачи, на данный момент: https://pastebin.com/jm8LDfQy
|
|
|
| 4 Курманкул Нурислам, 06 августа 2024 г. 20:59:20 |
| Для тогo, что бы проверять, может ли вообще жук выбраться из лабиринта, можно использовать два способа: 1. Предварительно запустить графовый алгоритм с клетки до которой нам нужно добраться, до начальной клетки. Или же запустить его в обратную сторону. И проверить то что мы посетили данную клетку или же нет. 2. Если количество шагов жука превысило 10^7, то жук уже точно не найдет выход. Данный факт гарантируется в условии. Дополнительно: Трюк с считанием количество клеток таких, что мы их посетили один раз не работает(Для тех кто посмотрел разбор с ютуба). Были добавлены новые тесты(14 тест и т.д), которые опровергают данное свойство. Т.к, возможны и те случаи, когда из-за приоритета движения жук зацикливается в определенной области, и количество клеток в которых мы побывали один раз становится равным нулю. И ваш код выводит -1, хотя на самом делe, выход есть.
|
|
|
| 5 Дмитрий Козырев, 18 апреля 2023 г. 2:29:56 |
| Приглашение в участии в зеркале этой задачи, где нужно составить лабиринт для Жука: https://codeforces.com/blog/entry/115144
|
|
|
| 6 Максимец Илья, 20 ноября 2020 г. 17:39:04 |
| Мне кажется или тут для проверки наличия выхода нужен дфс?
|
|
|
| 7 Зинов Вадим, 08 июня 2019 г. 9:41:19 |
Ну в условии ошибка... сказано, что если выход есть, то жук доберется до него менее чем за 10^7 шагов, что не соответствует 13 тесту. Поменял в условии 10000000 на 17000000 и все заработало) обманывать плохо ;)
"не более" и "менее" разные вещи. Попробуйте 10000001.
|
|
|
| 8 Кузин А В, 09 апреля 2019 г. 18:41:35 |
| Хм, прикольный поворот. Решил не писать проверку, а поставить ограничение, чтоб сэкономить время - не проходит. Сделал проверку, убрал ограничение - все заработало. Люблю задачи, в которых приходится бороться с ленью)
|
|
|
| 9 Иванов Григорий, 02 июля 2018 г. 17:03:10 |
Не подскажите, как вводить в данной задаче на C++?
Через cin удобно вводить с помощью getline.
|
|
|
| 10 Латкович Никита Валерьевич, 13 октября 2017 г. 23:07:07 |
Спустя 4 года, после того, как решил эту задачу на паскале, решил решить её на питоне...
Такой же алгоритм привёл к TLE на 9-ом тесте.
|
|
|
| 11 Бочаров Егор, 12 августа 2017 г. 13:08:42 |
Пробовал разные способы выхода, в случае если выхода нет. Прописывал if (difftime(t2, t1) > 0.9)
{
cout << -1;
return 0;
}
Но получал TL то на 11, то на 12.
В итоге прописал условие выхода , если шагов >2 000 000 и получил accepted
|
|
|
| 12 Четвертый Хокаге, 03 января 2017 г. 10:57:29 |
Если выхода нет, вот так можно остановить цикл
#include <ctime>
time_t t1, t2;
time(&t1)
while()
{
************
time(&t2);
if (difftime(t2, t1) > 0.9)
{
cout << -1;
return 0;
}
}
|
|
|
| 13 Черкасов Даниил Аркадьевич, 30 июня 2016 г. 12:10:54 |
| getline(cin,s); это c++ , s это строка
|
|
|
| 14 Алексеев Илья Алексеевич, 13 февраля 2016 г. 16:49:16 |
ДОПОЛНЕНИЕ К ПРЕВ СООБЩЕНИЮ :
ТК. BFS который ищет выход чтоб жука не закрыли не ругается если начиная справа от старта есть ПУТЬ ДЛЯ ВЫХОДА.
|
|
|
| 15 Алексеев Илья Алексеевич, 13 февраля 2016 г. 16:47:27 |
!!!У ВАС НЕПРАВИЛЬНЫЙ ГЕНЕРАТОР ЛАБИРИНТА(его можно сломать!!!)!!!!
если на начальную точку поставить стену , то жук начинает бежать вниз и можно сделать комнату в которой он будет бегать БЕСКОНЕЧНО ТК. BFS который ищет выход чтоб жука не закрыли не ругается если начиная справа от старта есть выход
!!!!!С ПОМОЩЬЮ ЭТОГО Я СЛУЧАЙНО СЛОМАЛ ОФ. САЙТ ЭТОГО ЖУЧКА. ИЗВИНЯЙТЕ, ЕСЛИ ЧТО)))
|
|
|
| 16 Хлопцев Андрей Алексеевич, 02 сентября 2015 г. 16:27:12 |
| Всегда первый ход вправо
|
|
|
| 17 Сайфутдинов Исмагил Айратович, 18 августа 2015 г. 12:09:37 |
6 Газиз, 08 сентября 2014 г. 2:00:25
кто-нибудь знает метод проверки достижимости, не используя алгоритмы на графах?
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Отсечение по времени
|
|
|
| 18 Юсюмбели Вячеслав Иванович, 18 марта 2015 г. 14:50:19 |
| У вас ошибка в условии "и заканчивает в координате (M-1, N-1)", а надо "и заканчивает в координате (N-1, M-1)"
|
|
|
| 19 Газиз, 08 сентября 2014 г. 2:00:25 |
| кто-нибудь знает метод проверки достижимости, не используя алгоритмы на графах?
|
|
|
| 20 Лукьянов Иван, 13 июня 2014 г. 15:19:42 |
| Кстати, а у вас есть строгое доказательство тому, что жучок, следуя данному алгоритму, всегда доберётся до выхода при условии, что хотя бы один путь к выходу есть?
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
