ŽUPANIJSKO NATJECANJE 2015/ Srednja škola, I. podskupina (1. i 2. razred) - 3. zadatak

Mirko i Slavko razvijaju igru za mobitele zvanu Angry Ducks.

Cilj igrača je da bacanjem bombi uništi što više meta na ploči.

Ploča za igru je pravokutnog oblika te se sastoji od R redaka i S stupaca.

Polja označena znakom '#' (ljestve) predstavljaju mete, a ona označena znakom '.' (točka) su prazna.

Bomba se baca tako da padne na jedno od polja unutar ploče, a kada padne ona eksplodira te uništava sve mete u istom retku i istom stupcu koji su udaljeni najviše 5 polja (uključujući i metu koja se možda nalazi na polju na koje je bomba pala).

Dakle, jedna bomba uništava mete na području oblika križa širokog i visokog 11 polja pa može uništiti najviše 21 metu.

Igrač ima točno dvije bombe na raspolaganju koje mora baciti na dva različita polja.

Napišite program koji će odrediti koliko je najviše meta moguće uništiti s te dvije bombe.

Ako neku metu uništavaju obje bombe, ona se, naravno, broji samo jednom.

Također, potrebno je odrediti na koliko je različitih načina moguće baciti dvije bombe tako da se uništi taj najveći mogući broj meta.

Prilikom određivanja broja različitih načina ne razlikujemo koja je prva, a koja druga bomba.

Na primjer scenarij ‘jedna bomba se baca na polje (2, 3), a druga na (5, 4)’ smatramo jednakim scenariju ‘jedna bomba se baca na polje (5, 4), a druga na (2, 3)’ te ga brojimo samo jednom.

Ulazni podaci

U prvom redu nalaze se dva prirodna broja, R i S (2 ≤ R, S ≤ 300) - broj redaka i broj stupaca ploče za igru.

U svakom od sljedećih R redova nalazi se po niz od točno S znakova ‘.’ ili ‘#’ koji opisuju jedan redak ploče.

Izlazni podaci

U prvi red ispišite najveći broj meta koje je moguće uništiti bacajući točno dvije bombe.

U drugi red ispišite ukupan broj različitih načina da se to napravi.

Napomena: Preporučamo da za računanje i ispis rezultata koristite 64-bitni cjelobrojni tip podataka (int64 u Pascalu, long long u C/C++).

Primjeri test​ podataka

Ulaz

5 6
...#..
..#.#.
.#...#
....#.
...#..

Izlaz

7
2

Objašnjenje

Pojašnjenje prvog primjera: Bombe bačene na polja označena slovom 'X' uništavaju sve mete na ploči.

Ulaz

7 7
#######
#.....#
#.....#
#.....#
#.....#
#.....#
#######

Izlaz

22
2

Objašnjenje

Pojašnjenje drugog primjera: Jedine mete koje nisu uništene su u donjem lijevom i gornjem desnom kutu. Drugi način uništavanja maksimalnog broja meta je da postavimo bombe u gornji desni i donji lijevi kut.

Ulaz

4 5
..#..
..#..
.#.##
..#..

Izlaz

6
31