AL15. Лабиринт

Условие

Матрица размера [latex]n*m[/latex] определяет некоторый лабиринт. B матрице элемент [latex]1[/latex] обозначает стену, а [latex]0[/latex] определяет свободное место. В первой строке матрицы определяются входы [latex]x_i[/latex], а в последней выходы [latex]y_i[/latex], [latex]i = 1, \ldots, k[/latex], [latex]k \leq n[/latex] которые должны быть нулевыми элементами.

Необходимо определить, можно ли:

а) провести [latex]k[/latex] человек от входа [latex]x_i[/latex] до выхода [latex]y_i[/latex] соответственно, [latex]i = 1, \ldots, k[/latex], таким образом, чтобы каждое свободное место посещалось не более одного раза.

б) то же, но человека можно выводить чеpез любой из выходов. Примечание: Движение в лабиринте осуществляется только по вертикали или горизонтали.

Входные данные

Числа [latex]n[/latex] и [latex]m[/latex] определяющие кол-во строк и столбцов соответственно, [latex]1 \leq n, m \leq 10^4[/latex]. Количество входов [latex]k[/latex]  равно кол-ву выходов, [latex]1 \leq k \leq min(1000, n)[/latex]. Число [latex]k[/latex] не является частью входных данных (не подается на вход программы).

Выходные данные

[latex]YES[/latex], если соответствующий набор маршрутов существует, [latex]NO[/latex] — в противном случае.

Замечания

  1. Легко заметить, что случай б) эквивалентен случаю а). Предположим, что [latex]k > 1[/latex] и мы провели первых [latex]i — 1[/latex] людей (возможно, никого) согласно условию а), [latex]1 \leq i < k[/latex]. Пусть человек под номером [latex]i[/latex] нарушил условие, например, вышел через выход с номером [latex]i + 1[/latex]. Тогда, т.к. его путь цельный и идет от самого первого ряда лабиринта до последнего, он образует «стену» из единичек, заблокировав выход [latex]i[/latex]. Тогда провести всех людей не возможно, ведь кол-ва входов и выходов равны. Следовательно, будем рассматривать как нашу задачу только случай а).
  2. Заполнение клеток каждого из пройденных маршрутов в матрице различными числами вместо единицы и функция
    не имеют отношения к поставленной задаче, так было сделано чтобы при желании можно было посмотреть, какой именно набор маршрутов программа нашла (см. код и тестовые данные, последняя колонка).

Тесты

№ теста Входные данные Выходные данные Пояснение (маршрут)
 1 6 8
1 0 1 0 1 1 0 1
1 0 1 0 0 0 0 1
1 0 1 1 0 0 1 1
1 0 0 0 0 0 0 1
1 0 0 1 1 0 0 1
1 0 0 1 1 1 0 1
 YES 1 a 1 b 1 1 c 1
1 a 1 b b c c 1
1 a 1 1 b c 1 1
1 a b b b c 0 1
1 a b 1 1 c c 1
1 a b 1 1 1 c 1
 2 5 7
1 0 0 0 1 1 0
0 0 0 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 0 0 0
0 0 0 1 1 1 0
YES 1 a b c 1 1 d
a a b c d d d
a b b c d 1 1
a b c c d d d
a b c 1 1 1 d
 3 7 7
1 1 0 0 1 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
1 1 1 1 0 1 0
YES 1 1 a b 1 1 1
a a a b 0 0 0
a a b b 0 0 0
1 a b b b b 0
a a a a a b 0
a a a 1 a b b
1 1 1 1 a 1 b
 4 5 5
0 1 0 1 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 1 0 1 0
 NO
 5 7 12
1 1 1 1 1 0 1 1 1 1 1 0
0 0 0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 1 1 0 1 1 1 0
0 1 1 0 0 0 1 1 1 0 0 0
1 0 1 0 0 0 1 0 0 0 1 0
0 0 0 0 0 0 1 0 0 1 1 0
1 1 1 1 1 0 1 1 1 1 1 0
 YES 1 1 1 1 1 a 1 1 1 1 1 b
0 0 0 1 a a 1 0 0 0 0 b
0 0 0 a a 1 1 0 1 1 1 b
0 1 1 a 0 0 1 1 1 0 0 b
1 0 1 a 0 0 1 0 0 0 1 b
0 0 0 a a a 1 0 0 1 1 b
1 1 1 1 1 a 1 1 1 1 1 b
 6 3 6
1 1 1 1 1 0
0 0 0 0 0 0
1 0 1 1 1 1
 YES 1 1 1 1 1 a
0 a a a a a
1 a 1 1 1 1
 7 10 10
0 1 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 0
0 1 0 1 0 0 0 0 1 0
0 1 0 1 0 0 1 0 1 0
0 1 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 1 0
0 1 1 1 1 1 1 0 1 0
0 0 0 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 0
 YES a 1 1 1 1 1 1 1 1 1
a 1 a a a a a a a a
a 1 a 1 1 1 1 1 1 a
a 1 a 1 a a a a 1 a
a 1 a 1 a 0 1 a 1 a
a 1 a 1 a 0 1 a 1 a
a 1 a a a 0 1 a 1 a
a 1 1 1 1 1 1 a 1 a
a a a a a a a a 1 a
1 1 1 1 1 1 1 1 1 a
 8 10 10
0 1 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 0
0 1 0 1 0 0 0 0 1 0
0 1 0 1 1 0 1 0 1 0
0 1 0 1 0 1 1 0 1 0
0 1 0 0 0 0 1 0 1 0
0 1 1 1 1 1 1 0 1 0
0 0 0 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 0
 NO
 9 6 7
1 1 1 1 0 0 1
0 0 0 1 0 0 1
0 1 0 0 0 0 1
0 0 1 0 0 0 1
1 0 0 0 0 1 1
1 1 0 0 1 1 1
 YES 1 1 1 1 a b 1
a a a 1 a b 1
a 1 a a a b 1
a a 1 b b b 1
1 a a b 0 1 1
1 1 a b 1 1 1
 10 1 5
0 0 0 0 0
 YES a b c d e

Алгоритм

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

  1. Попытаться провести человека согласно описанной выше стратегии.
  2. В случае успеха, отметить все ячейки, пройденные ним, как недоступные. Иначе — будем кидать исключение, ловить которое будем непосредственно в основной функции, при поимке — выводим [latex]NO[/latex] и завершаем работу программы.

За поиск маршрута отвечают 2 функции. Функция

возвращает стек координат (пар чисел), представляющих собой маршрут человека, или кидает исключение в случае его отсутствия. Функция только создает стек, помещает в него первую вершину и запускает рекурсивную функцию

отвечающую непосредственно за поиск, из точки входа с направлением движения вниз (т.к. из входа первый шаг можно совершить только вниз). Алгоритм поиска маршрута:

  1. Находим, в какую клетку мы попали при данном направлении. Определим все направления как подходящие константы и будем получать направление по формуле [latex]dir / 10, dir \mod 10[/latex], первая координата — по вертикали, вторая — по горизонтали. Так, например, для [latex]down = 10[/latex] получим вектор [latex](1, 0)[/latex], соответствующий перемещению на одну ячейку вниз в матрице (для остальных направлений значения подобраны аналогично).
  2. Проверяем, можем ли мы находиться в этой ячейке, если нет (она занята или находится вне матрицы) — не ищем дальше, возвращаем [latex]false[/latex].
  3. Добавляем координаты ячейки в стек route, проверяем, является ли данная точка выходом, если да — завершаем поиск успешно ([latex]true[/latex]).
  4. Составим массив направлений, от наиболее до наименее приоритетных, в зависимости от предыдущего направления. Например, текущее направление было [latex]down[/latex], мы пришли сверху, лучше всего будет попробовать пойти влево, иначе снова вниз, иначе вправо, наверх нельзя (уже были):
    Для других направлений — рассуждения аналогичны.
  5. Поочередно вызовем поиск из новой точки в каждом из направлений в порядке приоритета, при нахождении пути оставшиеся направления (с меньшим приоритетом) не рассматриваем, возвращаем [latex]true[/latex].
  6. Если ни в одном из направлений нельзя попасть к выходу (тупик) — удаляем вершину из стека, возвращаем [latex]false[/latex].

Код

 

Ссылки

Код для тестирования на ideone.

Добавить комментарий