Državno natjecanje iz informatike 2017. / Srednja škola / Prva podskupina (1. i 2. razred) / Drugi dan - 1. zadatak

Svake noći kroz Mirkovo dvorište migriraju mačke lutalice oštećujući mu pritom ciklame i ostalo ukrasno cvijeće. Mirkovo dvorište se sastoji od polja kvadratnog oblika organiziranih u \(n\) redaka i \(m\) stupaca. Retci su označeni brojevima od \(1\) do \(n\) odozgo prema dolje, a stupci brojevima od \(1\) do \(m\) slijeva na desno. Neka polja su travnata (označena velikim slovom X) dok su neka betonirana (označena znakom .).

Mačka migrira tako da preskoči ogradu te skoči na polje \((1,1)\) u gornjem-lijevom kutu dvorišta. Zatim se kreće prema donjem-desnom kutu tako da se u svakom koraku pomakne na susjedno polje na desno ili na susjedno polje prema dolje. Nakon točno \(n+m−1\) koraka mačka dolazi do polja \((n,m)\) te preskače ogradu i izlazi iz dvorišta. Mačka se kreće isključivo po travnatim poljima — baš nikada ne stupi nogom na betonirano polje. Mirko je odlučio betonirati neka travnata polja kako bi bilo nemoguće da mačka prođe kroz dvorište na opisani način. Također, Mirko želi da polja koja će betonirati budu u istom stupcu.

Težina blokade u stupcu \(j\) se označava s \(t_j\) i definira se kao najmanji broj travnatih polja u tom stupcu koje je potrebno betonirati da mačka ne može proći kroz dvorište na opisani način. Odredite težinu blokade \(t_j\) za stupce \(j =2,3,...,m−1\) (dakle za sve stupce osim prvog i zadnjeg).

Ulazni podaci

U prvom redu nalaze se prirodni brojevi \(n\) i \(m\) \((1 \leq n,m \leq 2000)\) – dimenzije dvorišta. U svakom od sljedećih n redova nalazi se niz od točno \(m\) znakova koji predstavlja jedan redak dvorišta. Travnato polje je označeno velikim slovom X, a betonirano znakom . (točka).

Izlazni podaci

Ispišite \(m−2\) redova. U \(j\)-ti red ispišite \(t_j+1\) — traženu težinu blokade stupca \(j +1\).

Bodovanje

U test podacima vrijednim \(40\%\) bodova vrijedi \(n,m \leq 400\).

Primjeri test podataka

Ulaz

6 8
XXXXXXXX
XXXX....
XXXXXX..
...XXXXX
...XXXXX
X.....XX

Izlaz

3
3
1
3
2
2

Ulaz

5 7
XXXX...
X..X...
XXXXXXX
X..X..X
XXXXXXX

Izlaz

3
3
2
2
2

Objašnjenje

Težina blokade u stupcu \(4\) je jednaka \(2\) — jedan optimalan odabir \(2\) polja za betoniranje je dan na slici.