Državno natjecanje iz informatike 2021. / Prva podskupina (1. i 2. razred) – drugi dan natjecanja - 2. zadatak

Arheolozi su otkrili postojanje dosad nepoznatog hrama u drevnom Babilonu.

Njihovo područje iskapanja možemo zamisliti kao dvodimenzionalnu matricu s R × S polja.

Poznato je da je hram bio oblika pravokutnika te je tlocrtom zauzimao neku podmatricu promatranog područja.

Arheolozi nisu sigurni na kojim se točno poljima nalazio hram.

Međutim, za svako polje matrice odredili su odgovarajuću vjerojatnost. Tako su podijelili polja u tri kategorije: ona na kojima se hram sigurno nalazio, ona na kojima se možda nalazio i ona na kojima se sigurno nije nalazio.

Pomozite arheolozima i napišite program koji će s obzirom na ove informacije izračunati broj mogućnosti za poziciju hrama, tj. broj mogućih pravokutnika koji bi odgovarali njihovim nalazima.

Ulazni podaci

U prvom su retku prirodni brojevi R i S (1 ≤ R, S ≤ 2000) iz teksta zadatka.

Idućih R redaka sadrži po S znakova koji opisuju područje iz teksta zadatka.

Znak 1 označava polje gdje se nalazio hram, znak 0 polje gdje se nije nalazio, a znak ? (upitnik) polje gdje se hram možda nalazio.

Izlazni podaci

U jedini redak ispišite traženi broj mogućih položaja hrama.

Primjer zadatka

Ulaz

3 3
0?0
?1?
0?0

Izlaz

7

Objašnjenje

Pojašnjenje prvog probnog primjera: Sedam mogućih položaja hrama prikazano je na donjim slikama. Svaka prikazuje jedan mogući položaj hrama koji se nalazi na podcrtanim poljima:

Ulaz

5 5
?1111
?1111
??11?
?????
?0???

Izlaz

4

Objašnjenje

Pojašnjenje drugog probnog primjera: Jedan mogući položaj hrama je pravokutnik koji zauzima cijela prva četiri reda. Preostala tri moguća položaja su manji pravokutnici unutar navedenog