Županijsko natjecanje 2014. / Osnovna škola (7. razred) - 3. zadatak

Maja slaže svoju ploču za Potapanje brodova. (Ako ne znaš igru, nema veze.) Ploča ima \(R\) redaka i \(S\) stupaca. Na ploču se postavljaju samo sljedeći brodovi:

• jednomotorac, brod koji zauzima samo jedno polje kao na slici,
• dvomotorac, zauzima dva uzastopna polja kao na slici:
• tromotorac, zauzima tri uzastopna polja kao na slici:
• četveromotorac, zauzima četiri uzastopna polja kao na slici:

Svaki od ovih brodova, osim vodoravno, može biti postavljen i okomito!

Zadana je ploča na kojoj su možda već postavljeni neki brodovi (a može biti i prazna). Zadan je i brod koji Maja sljedeći postavlja na ploču. Pomozi Maji i reci joj na koliko načina ga ona može postaviti, tako da taj brod ne dodiruje ni jedan već postavljeni brod?

Dva broda se dodiruju ako je neko polje, na kojem je dio prvoga broda, susjedno nekom polju na kojem je dio drugoga broda. Polja mogu biti susjedna u osam smjerova, koji su prikazani na slici.

Ulazni podaci

U prvome retku nalaze se prirodni brojevi \(R\) i \(S\) \((1 \leq R, S \leq 10)\), dimenzije ploče.

U sljedećih \(R\) redaka nalazi se po \(S\) znakova. Ovi znakovi opisuju trenutno stanje ploče. Znak . (točka) predstavlja prazno polje, a znak # (ljestve) predstavlja polje na kojemu se već nalazi neki brod.

Sljedeći redak sadrži prirodan broj \(K\) \((1 \leq K \leq 4)\) koji označava duljinu broda koji Maja želi postaviti.

Izlazni podaci

U jedini redak ispiši traženi broj načina da Maja postavi brod.

Bodovanje

U test podacima ukupno vrijednima \(18\) bodova, brod koji Maja postavlja bit će jednomotorac \((K = 1)\).

Od ostalih test podataka, u podacima ukupno vrijednima \(18\) bodova, ploča bit će takva da će brod biti moguće postaviti samo vodoravno, a u podacima ukupno vrijednima također \(18\) bodova, ploča bit će takva da će brod biti moguće postaviti samo okomito.

Primjeri test podataka

Ulaz

3 4
....
..#.
....
1

Izlaz

3

Ulaz

3 5
#....
.....
..##.
2

Izlaz

2

Objašnjenje

Maja ima sljedeće mogućnosti:

Ulaz

5 3
..#
..#
...
...
...
3

Izlaz

5

Objašnjenje

Maja ima sljedeće mogućnosti: