Programozás‎ > ‎Feladatok‎ > ‎

Játék (NT)

Tekintsük azt az egyszemélyes játékot, amelyet N sorból és M oszlopból álló négyzetrácsos táblán játszanak. Minden mező vagy üres, vagy csapda. Egy bábut kell mozgatni a táblán. A bábu kezdetben a tábla bal felső sarkában van, és a jobb alsó sarokba kell eljuttatni az alábbi lépés-szabályt betartva:
  • Csak olyan mezőre lehet lépni, ahova még nem lépett a bábu.
  • Csapda mezőre nem lehet lépni.
  • Csak a négy szomszédos mező valamelyikére lehet lépni.
  • Egy lépésben csak jobbra, vagy lefelé lehet lépni. 

Feladat

Készíts programot, amely kiszámítja, hogy hányféle képen lehet eljuttatni a bábut a bal felső sarokból a jobb alsóba!

Bemenet

A jatek.be szöveges állomány első sorában két egész szám van, a sorok N és oszlopok M száma (1 <= N <= 10, 1 <= M <= 20). A további N sor mindegyike M egész számot tartalmaz egy-egy szóközzel elválasztva. Minden szám vagy 0, vagy 1. A sorban az i-edik szám 1, akkor a megfelelő mező csapda, egyébként a mező üres.

Kimenet

A jatek.ki szöveges állomány egyetlen sora egy egész számot tartalmazzon, azt, hogy hányféleképpen lehet eljuttatni a bábut a bal felső sarokból a jobb alsóba!

Példa

Bemenet  Kimenet
5 6
0 0 0 0 0 0
0 1 0 0 1 0
0 0 1 0 0 0
1 0 1 0 0 0
0 0 0 0 1 0
7


Tesztadatok

Címkék

A feladat forrása: NTOITV 2011. 2. forduló, 9-10. évfolyam
Algoritmusok: 

megoldás