|
Количество путей в лабиринте
(Время: 1 сек. Память: 16 Мб Сложность: 38%)
Карта лабиринта представляет собой квадратное поле размером N×N. Некоторые квадраты этого поля запрещены для прохождения. Шаг в лабиринте – перемещение из одной разрешенной клетки к другой разрешенной клетке, смежной с первой по стороне. Путь – это некоторая последовательность таких шагов. При этом каждую клетку, включая начальную и конечную, можно посещать несколько раз.
Требуется написать программу, которая подсчитает количество различных путей из клетки (1, 1) в клетку (N, N) ровно за K шагов (то есть оказаться в клетке (N, N) после K-го шага).
Входные данные
Входной файл INPUT.TXT содержит в первой строке числа N и K, разделенные пробелом (1 < N ≤ 15, 0 < K ≤ 30). Следующие N строк, по N символов в каждой, содержат карту лабиринта, начиная с клетки (1, 1). Символ «0» означает не запрещенную для прохождения клетку, а символ «1» - запрещенную. Начальная и конечная клетки всегда разрешены для прохождения.
Выходные данные
Выходной файл OUTPUT.TXT должен содержать количество возможных различных путей длины K. Во всех тестах это значение не будет превышать 2147483647.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 6
000
101
100 | 5 |
| 2 | 2 8
01
10 | 0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
