Ограничения: время – 5s/10s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение 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
XIV Всеукраинская олимпиада по информатике, 2001