НачалоПодразделы
Другие разделы
| 1594. Big number |
| 1595. Вычеркивание двух |
| 1596. Подарок |
| 1597. Поиск степени |
| 1599. Деревни |
| 1600. Мавританские карты |
Дата и время
22/11/2024 17:21:41
1598. Левый лабиринт
Левый лабиринт
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 04/07/2011 | Лето 2011 - дорешивание (05F) |
| 08/07/2011 | Лето 2011 - 5 (F) |
| 07/07/2021 | Лето 2021-5 (E) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В спортзале размером `N`x`M` метров построили современный аттракцион под названием "Левый лабиринт". Для этого на полу
спортзала с интервалом в 1 метр начертили линии, параллельные стенам спортзала. Таким образом, спортзал разбили
на `N`x`M` клеток. Дальше некоторые из этих клеток покрасили в черный цвет. Аттракцион заключается в том, что участника
ставят в некоторой клетке спортзала и просят как можно быстрее добежать до некоторой другой клетки. При этом
накладываются следующие условия:
- Участнику запрещено ходить по черным клеткам.
- Придя в какую-то клетку, участник может пойти либо прямо, либо налево, либо направо (если в соответствующем направлении клетка не покрашена в черный цвет): ходить назад, а также ходить по диагонали запрещается.
- За все время пути участнику разрешается повернуть направо (то есть пойти из текущей клетки направо относительно того, откуда он пришел в данную клетку) не более `K` раз.
- В начальной клетке участник может встать лицом в ту сторону, в какую ему захочется. С какой стороны участник прибежит в конечную клетку также не важно.
Известно, что на то, чтобы перебежать из клетки в соседнюю, участник тратит ровно 1 секунду.
Требуется вычислить минимальное время, за которое участник сможет достичь конечной клетки.
Ввод
Во входном файле сначала записано число `K` — количество разрешенных поворотов направо (целое число из диапазона
от 0 до 5), затем записаны числа `N` и `M`, задающие размеры спортзала — натуральные числа, не превышающие 20.
Далее записано `N` строк по `M` чисел в каждой. Число 0 обозначает непокрашенную клетку, число 1 — покрашенную,
число 2 — клетку, откуда стартует участник и число 3 — клетку, куда нужно добежать (клетки, помеченные 2 и 3
являются непокрашенными). В лабиринте всегда есть ровно одна начальная клетка и ровно одна клетка, в которую
нужно попасть.
Вывод
В выходной файл выведите минимальное время, за которое можно добраться в конечную клетку.
Если попасть в конечную клетку с соблюдением всех условий нельзя, выведите `–1`.
Пример ввода 1
1 5 5 2 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 1 3 1 0 0 1
Пример вывода 1
12
Пример ввода 2
0 3 4 2 0 0 0 1 1 1 0 3 0 0 0
Пример вывода 2
-1
