Лабиринт

Условие:

           Имя входного файла:                стандартный поток ввода
           Имя выходного файла:             стандартный поток вывода
           Ограничение по времени:      2 second
           Ограничение по памяти:        64 мегабайт
Задан лабиринт [latex] N \times N [/latex], некоторые клетки которого могут быть заняты. Дан путь робота длины [latex] k [/latex] по этому лабиринту без указания его начального положения. Известно, что робот до начала движения стоит в одной из свободных клеток. Необходимо определить наименьшее количество передвижений по пути, после которого можно точно определить, где находится робот.

Формат входного файла:

Первая строка входного файла содержит два целых числа через пробел $$ N (1 \leq  N \leq  100) $$ и $$k  (0 \leq  k \leq  10^{5}) $$. В следующих [latex] N [/latex] строках задана карта лабиринта как совокупность 0 и 1 без пробелов: 1 – занятая клетка, 0 – свободная. В последней строке дана последовательность из $$ k  (0 \leq  k \leq  10^{5} ) $$ символов. Символы задают движение робота по лабиринту: символ [latex] U [/latex] — вверх, [latex] D [/latex] — вниз, [latex] R [/latex] —вправо, [latex] L [/latex] — влево. Других символов в строке передвижений нет, все символы в верхнем регистре латиницы.

Формат выходного файла:

В единственной строке выходного файла выведите единственное целое число не меньше нуля — наименьшее количество передвижений по пути, после которого можно точно определить местоположение робота. Если ответ не существует, либо входные данные некорректны, выведите -1.

Тесты:

Входные данные Выходные данные
1
 2 0
 11
 01
 0
2
 2 0
 11
 11
 -1
3
2 1
11
01
R
 -1
4
3 3
000
010
000
RDU
2
5 5 5
00010
10001
00100
10100
01101
RDUUU
4

Решение:

Если попробовать решить эту задачу «в лоб», то решение не будет удовлетворять пределу по времени, так как в худшем случае, нам надо перебрать $$ 10^{4} $$ возможных начальных позиций и совершить из них  $$ 10^{5} $$  ходов, что в результате дает  $$ 10^{9} $$ операций.

Решение «в лоб»:

  • Заведем список позиций в лабиринте, которым соответствуют элементы матрицы, в которые может попасть робот. В изначальном состоянии, без просмотра пути передвижения робота, это будут все позиции в лабиринте, где значение равно $$ 0 $$. После чего, проходя путь робота по шагам, будем для всех позиций в списке проверять:
    • Если мы вышли за границу матрицы, или в клетке, в которую мы собираемся перейти стоит $$ 1 $$, тогда удаляем эту позицию, поскольку она для нас недостижима.
    • Иначе ничего не делаем.
  • Если количество текущих вариантов пути стало равным $$ 1 $$, то мы запоминаем количество ходов при которой была достигнута данная ситуация.
  • Так будем делать до тех пор, пока робот закончил свой путь.
  • Если после всех проделанных нами операций остался один вариант полностью пройденного пути, тогда ответ найден. А именно это будет ход, после которого у нас кол-во удовлетворяющих позиций стало равным $$ 1 $$. В любом другом случае ответ нельзя определить однозначно.

Другая идея состоит в том, чтобы построить карту «переходов», в которой будет храниться номер хода, на котором робот впервые попал в эту клетку и ее координаты. Эта карта играет роль некоторого шаблона полного пути робота и «накладывая» его на каждый элемент матрицы в качестве начальной позиции, мы проверяем мог ли данный элемент матрицы служить «пунктом отправления» робота. Если такой элемент есть и он единственен, значит, можно однозначно определить начальное положение робота, но для того чтобы определить минимальное количество требуемых ходов-нужно последовательно удалять последние ходы из карты, «накладывая» изменившийся шаблон на каждый элемент, до тех пор, пока количество элементов удовлетворяющих шаблону не возрастет. Что значит, что мы получим номер решающего хода после которого судьба робота решится однозначно, значит ответом будет предыдущий ход. Стоит отметить, что если в карте останется всего лишь один элемент (соответствующий первому ходу), то расположение робота определялось однозначно первым ходом.

Submission.

 

Маша Лукьянова
Маша Лукьянова

Latest posts by Маша Лукьянова (see all)

6 thoughts on “Лабиринт

  1. — Нужно разобраться с пробелами. Например, перед закрывающей кавычкой, запятой, двоеточием пробелы не ставят. Можно прочесть статью Википедии про пробел.
    — В коде тоже проблемы с пробелами, но не такие неприемлемые.
    — Пожалуйста, не используйте стилистических настроек (цветов и т.п.) — только семантические теги. Настройки внешнего вида будут общими для всего сайта.
    — Вы пишите «должен смочь». Это не самое удачное словосочетание — оставьте только «должен».
    — Как минимум первое предложение слишком «наверчено» с двумя «зачем». Нужно выразить мысль чётче.
    — Ссылка на submission не доступна обычному читателю.
    — Рубрика «Организационные» излишня.
    — Нужно написать откуда взята задача и указать автора, если он известен.

  2. – Пробелы исправлены (вроде бы все).
    – Цветовые настройки убрала.
    – Первое предложение исправлено.
    – Ссылку на submission удалила.
    – Рубрику «Организационные» убрала.
    – Добавила ссылку на условие задачи. Автор неизвестен.

  3. Лучше. Но всё ещё плохо.
    — «задача не зайдет по времени» — решение не зайдёт, не задача
    — «будет за…» -> потребует примерно 109 операций. И нужно коротко объяснить или хоть намекнуть, как получилась эта оценка
    — Везде по тексту » точки матрицы» нужно заменить на «клетки лабиринта». Я понимаю, что Вы представили себе лабиринт в виде матрицы, просто не пишите об этом. Вот только точек у матрицы нет, есть элементы. Т.е. (кроме правильных терминов) нужно обязательно писать если Вы сделали переход от условий задачи к какой-то модели (матричной, графовой и т.п.)
    — «осталась одна точка, которая смогла пройти весь путь». Я даже не знаю, что тут посоветовать. До чтения пояснения мне было понятно, как решать задачу 🙂

    У меня такое предложение. Придите как-нибудь в среду на занятия факультатива и со мной или с Александром Сергеевичем пройдитесь по тексту пояснения.

  4. Что же, теперь текст переделан и стал более понятен. По крайней мере мне понятно описание алгоритма «в лоб» и в общих чертах Вашего алгоритма — основная идея вполне понятна. Но вот что такое карта конкретно и тем более как она конкретно накладыввается мог только догадываться — пока не посмотрел на код. Не знаю, может у Игоря Евгеньевича будет другое впечатление — но мне последний абзац показался понятным, но не исчерпывающим.

    А теперь по сути задачи. Вы можете оценить сложность Вашего алгоритма (который не «в лоб»)? Вы уверены, что он работает быстрее? Кстати, у Вас была возможность проверить задачу на сервере kpi и она получила вердикт Accepted?

  5. Я добавила скрин с codeforeces. Ссылку кинуть не могу, потому что, чтобы открыть ее, нужно сдать задачу, т.е. ссылка на submission не доступна обычному читателю.
    Время с которым мое решение зашло составляет 60 мс в диапазоне от 30 мс до 90 мс.
    По поводу сложности я не могу дать точную оценку, я знаю, что решение заходит, в следствии того, что оно очень быстро сходится (даже в нулевой матрице 100×100).