`Всеукраїнський центр проведення олімпіад в мережі Інтернет
  1. Mines

Задача МИННОЕ ПОЛЕ (MINES).

  Холодным, дождливым, осенним вечером уходя от погони, Шпион переходит минное поле. К счастью, у него есть карта, где отмечены мины. Эта карта нарисована на листке бумаги в клетку, вырванном из школьной тетради любимого сыночка Шпиона. Каждая клетка изображает квадратный метр поля, клетки с минами помечены красным крестиком.
    Чтобы запутать следы, Шпион передвигается прыжками: на два метра вперед и метр в сторону, или на метр вперед и два в сторону (как шахматный конь, только назад двигаться нельзя, см. рисунок).
    Сколько существует путей через минное поле, которые начинаются с самого верхнего ряда клеток и заканчиваются на самом нижнем.
    Напишите программу MINES, которая читает карту c клавиатуры и выводит число путей на экран.


  

 Формат ввода:

 M  и N   число строк и столбцов в карте. Pij=1 , если в клетке нет мины, и Pij=0  , если она заминирована.

 Ограничения:

1

П ример:

Ввод:

5 4
1 1 1 1
0 1 0 1
1 0 1 0
1 0 1 0
1 1 0 1

Вывод:

8

© LIKT 1998-2024