printРабочее место участника

printЗадачи

830. Лабиринт

Ограничения: время – 5s/10s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Чтобы добраться до источника живой воды, путешественник должен пройти через лабиринт. Не всегда существует путь к источнику, но путешественник может проходить сквозь стены, используя магию. К сожалению, путешественник может использовать магию только ограниченное количество раз, а до источника необходимо добраться как можно быстрее.
Лабиринт имеет форму квадрата, который состоит из `N`x`N` квадратных клеток, внутри которого вдоль сторон клеток могут быть расположены стены.
В каждый момент времени путешественник может находиться в одной и только в одной клетке лабиринта.
Одним ходом считается перемещение путешественника в соседнюю по горизонтали или по вертикали клетку. Путешественник может `K` раз проходить сквозь стену и не может выходить за пределы лабиринта.
Составьте программу, которая вычислит минимальное количество ходов, за которое путешественник может добраться до источника с координатами `(P,\ Q)`, начав путь в клетке с координатами `(1,\ 1)`.
Входной файл в первой строке содержит числа `N`, `K`, `P`, `Q` (`2\ ≤\ N\ ≤\ 200`, `0\ ≤\ K\ ≤\ 250`, `1\ ≤\ P,\ Q\ ≤\ N`). Следующие `N-1` строк содержат по `N` целых чисел – признаков наличия горизонтальных стен между клетками. Следующие `N` строк содержат `N-1` целых чисел  – признаков наличия вертикальных стен между клетками. 0 означает отсутствие стены, 1 – присутствие.
Единственная строка выходного файла должна содержать найденное минимальное количество ходов, или число `-1`, если путь найти не удалось.

Пример ввода

3 1 2 3
0 0 0
0 1 0
1 0
1 0
0 0

Пример вывода

3
XIV Всеукраинская олимпиада по информатике, 2001
loading