Državna razina / Primjena algoritama OŠ 2022. / Osnovna škola (8. razred) - 3. zadatak

Godina je 2100.! Nakon brojnih neuspjelih pokušaja zaustavljanja klimatskih promjena, sada svijetom haraju požari i poplave, a naš jedan i jadan Kile se nakon burne noći vraća kući. Kiletov kvart možemo zamisliti kao NxM tablicu. Na polju označenom slovom "D" nalazi se "Dvorište", malo mjesto velikih zbivanja, gdje se Kile trenutno nalazi, a njegova slatka kuća na polju označenom slovom "K". No, na tablici se nalaze i mnogi požari označeni znakom "#" (ljestve) te poplave označene znakom "O" (slovo O). Sva ostala polja označena su s ".". U svakoj sekundi dogode se tri događaja. Prvo Kile odluči želi li se pomaknuti na jedno od četiri susjedna polja s kojima dijeli stranicu ili će ostati na istom polju, zatim se poplava sa svog polja proširi na susjedna četiri, pritom šireći se i na moguće požare pretvarajući ih pritom u poplave. Na kraju, požari će se proširiti na četiri susjedna polja, ako se na njima već ne nalazi poplava. Ako se požar proširi na polje gdje se nalazi Kile, Kile neće moći doći kući. Kile srećom sa sobom ima i mali brodić na napuhavanje što mu omogućuje kretanje po slobodnim i poplavljenim poljima, no ne postoji način da se kreće kroz požare. Kileta sada zanima može li stići kući, te ako može nakon koliko najkraće vremena može to učiniti. U slučaju da ne može, potrebno je ispisati -1.

Ulazni podaci

U prvom su retku prirodni brojevi N (1 ≤ N ≤ 300) i M (1 ≤ M ≤ 300) iz teksta zadatka. U sljedećih N redaka nalazi se tablica opisana na način iz teksta zadatka.

Izlazni podaci

Ispiši najkraće vrijeme nakon kojeg Kile može stići doma, odnosno -1 ako ne može stići doma.

Bodovanje

U primjerima vrijednim 10 bodova, neće se pojavljivati polje s požarom. U primjerima vrijednim dodatnih 20 bodova, neće se pojavljivati polje s poplavom. U primjerima vrijednim dodatnih 30 bodova, vrijedit će N ≤ 50 i M ≤ 50.

Primjer zadatka

Ulaz

4 4
...K
#...
....
O.D.

Izlaz

6

Ulaz

5 6
......
..D..#
..##K.
......
..O...

Izlaz

-1

Ulaz

8 8
D#...#..
....#...
O.......
....##..
.#......
........
....#...
.#...O.K

Izlaz

14

Opis prvog probnog primjera:

Kretanje požara i poplave možemo pratiti po koracima u tablicu. Kile može stići kući sljedećim kretanjem: