ПОШУК ОЛІМПІАДИ - Показати
Лабиринт

 

 

Чтобы добраться до источника живой воды, путешественник должен пройти через лабиринт. Не всегда существует путь к источнику, но путешественник может проходить сквозь стены, используя магию. К сожалению, путешественник может использовать магию только ограниченное количество раз, а до источника необходимо добраться как можно быстрее.

Лабиринт имеет форму квадрата, который состоит из NxN квадратных клеток, внутри которого вдоль сторон клеток могут быть расположены стены.

В каждый момент времени путешественник может находиться в одной и только в одной клетке лабиринта.

Одним ходом считается перемещение путешественника в соседнюю по горизонтали или по вертикали клетку. Путешественник может K раз проходить сквозь стену и не может выходить за пределы лабиринта.

Задание

Составьте программу MAZE, которая вычислит минимальное количество ходов, за которое путешественник может добраться до источника с координатами (P, Q), начав путь в клетке с координатами (1, 1).

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

Входной текстовый файл MAZE.DAT в первой строке содержит числа N, K, P, Q (2<=N<=200, 0<=K<=250, 1<=P,Q<=N). Следующие N-1 строк содержат по N целых чисел - признаков наличия горизонтальных стен между клетками. Следующие N строк содержат N-1 целых чисел - признаков наличия вертикальных стен между клетками. 0 означает отсутствие стены, 1 - присутствие.

Пример входного файла

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

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

Единственная строка выходного текстового файла MAZE.SOL должна содержать найденное минимальное количество ходов, или число -1, если путь найти не удалось

Пример выходного файла

3