Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 500/500/500/500 ms. Memory limit 1000/1000/1000/1000 Kb.
Исследователь Вася на своем корабле потерпел крушение около необитаемого острова размером M×N. При крушении он успел подать сигнал «SOS». Ему ответил неизвестный корабль и указал время и место, где будет его ждать на острове, так получилось по причине шторма, бушующего в том регионе.При изучении карты острова, которую Вася успел взять с собой, выяснилось, что на острове имеются непроходимые районы.
Высадился Вася в противоположном от места эвакуации части острова. Времени у него немного, всего он может побывать не более, чем в M+N-1 районах острова, включая начальный и конечныйрайон на своем пути, то есть с каждым переходом расстояние до места спасения должно уменьшаться. Помогите Васе найти количество различных маршрутов, ведущих к спасению.
Формат входных данных
Первая строчка входных данных содержит натуральные числа M≤1000 и N≤1000.
Далее идет план острова в виде M строчек из N символов в каждой. Один символ соответствует одномурайону острова: если символ равен1, то в данный район острова можно попасть, если он равен0, то он считается непроходимым. Все символы разделены пробелом (или двумя, а может и тремя. Кто может знать?).Первоначальное положение Васи – левый нижний угол (первый символ последней строки). Первоначальный и конечный пунктвсегда равны 1.
Формат выходных данных
Программа должна вывести количество маршрутов, ведущих Васю к месту спасения через M+N-1 районов острова, или слово «no», если таких маршрутов не существует.
Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2x109.
|
Ввод 1
|
Ввод 2
|
3 5
11111
10101
11111
|
3 5
11101
10101
10101
|
|
Вывод 1
|
Вывод 2
|
|
3
|
no
|
Для отправки решений необходимо выполнить вход.
|