Вот такая задачка:Вам дан робот и число N.Нужно придумать строку из букв R,L,U,D так чтобы если впустить робот в лабиринт NxN(клетчатая доска) где в некоторых узлах есть стены,тогда робот должен пройти все клетки лабиринта хотя бы по одному разу.Команды R,L,U,D приказывают идти вправо,влево,вниз,вверх соосветсвенно.Если приказывают идти сквозь стену то робот просто стоит на месте.Роботу может попасть в начале в любую клетку любого лабиринта.Придумайте строку.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3803 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3627 |
| 4 | ecnerwala | 3584 |
| 5 | orzdevinwang | 3573 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | Radewoosh | 3542 |
| 9 | jqdai0815 | 3532 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 163 |
| 2 | maomao90 | 160 |
| 3 | adamant | 159 |
| 4 | maroonrk | 152 |
| 5 | -is-this-fft- | 150 |
| 6 | atcoder_official | 148 |
| 6 | SecondThread | 148 |
| 8 | nor | 147 |
| 9 | TheScrasse | 146 |
| 10 | Petr | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 08.07.2024 21:36:02 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Я так понимаю, связность лабиринта гарантируется?
Я знаю, как придумать такую строку. Рассмотрим всевозможные ситуации (ситуация = лабиринт + клетка, в которую мы попали).
Рассмотрим первую ситуацию и выпишем последовательность, которая позволит нам пройти все клетки в этой ситуации. При этом во всех остальных ситуациях наблюдаем, где мы оказались.
Когда мы прошли все клетки в первой ситуации, переходим ко второй и выписываем последовательность, которая позволит пройти все ранее не пройденные клетки (начиная из клетки, в которой мы оказались после обхода первой). При этом следим за тем, где мы оказываемся во всех ситуациях, начиная с третьей.
И так далее.
Да связность гарантируется.У меня такая же строка.Существует ли строка поменьше?
Похожая задачка: http://www.braingames.ru/index.php?path=comments2&puzzle=430 Судя по комментам, авторское решение такое же.
О положении стен нам ничего неизвестно?
Да
Рассуждая примерно как здесь, можно получить, что случайная строка длины
(возможно, степень логарифма неправильная, это навскидку) с высокой вероятностью подходит для всех лабиринтов и для всех стартовых положений.
UPD: здесь n -- количество вершин, если n -- размер лабиринта, то длина равна
.
Задача B с NEERC 2008 (http://mirror.codeforces.com/gym/100286) похожа на вашу. У нас зашёл рандом, но там ограничения уж совсем маленькие по-моему. P.S: там интерактив, решать можно совсем не рандомом, т.к. мы ещё получаем информацию, попали ли мы в стену. Но для проверки решения (если Вы не взяли эту задачу откуда-то, а придумали сами) вполне сойдёт.
Да очень похожая.Но интерактивность очень даже облегчает поставленную задачу.Задачу нам давали на тренировках(по математике) года 2 назад.Мне стало очень интересно есть ли другое решение.Например i раз поторяем что-то,i+1 еще что-то и.т.д.