Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Количество путей в лабиринте

(Время: 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.TXTOUTPUT.TXT
13 6
000
101
100
5
22 8
01
10
0

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ