Лабиринт

Условие:

           Имя входного файла:                стандартный поток ввода
           Имя выходного файла:             стандартный поток вывода
           Ограничение по времени:      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.

 

Related Images: