Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

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

(Время: 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

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

[Обсуждение] [Все попытки] [Лучшие попытки] [Решение]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 ЕГЭ по информатике
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2007 / 2008 1 тур
 2007 / 2008 2 тур
 2007 / 2008 3 тур
 2008 / 2009 1 тур
 2008 / 2009 2 тур
 2008 / 2009 3 тур
 2009 / 2010 1 тур
 2009 / 2010 2 тур
 2009 / 2010 3 тур
 2010 / 2011 1 тур
 2010 / 2011 2 тур
 2010 / 2011 3 тур
 2011 / 2012 1 тур
 2011 / 2012 2 тур
 2011 / 2012 3 тур
 2012 / 2013 1 тур
 2012 / 2013 2 тур
 2012 / 2013 3 тур
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 2020 / 2021 7-8 классы
 2020 / 2021 9-11 классы
 2021 / 2022 7-8 классы
 2021 / 2022 9-11 классы
 2022 / 2023
 2023 / 2024
 2024 / 2025
 A. Неглухой телефон
 B. День программиста
 C. Таблица умножения
 D. Количество путей в лабиринте

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru