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