Slikar
Zli Kaktus car dočepao se Čarobne bačvice i poplavio Čudesnu šumu! Slikar Paleta i tri mala ježa sada se moraju što brže vratiti do Dabrove kolibe, gdje će se skloniti od bujice.
Karta Čudesne šume se sastoji od R redaka i S stupaca. Na karti su prazna polja označena znakom '.',polja pokrivena vodom znakom '*', a polja na kojima se nalazi stijena znakom 'X'. Također, dva su istaknuta polja, polje na kojem se nalazi Dabrova koliba (označeno znakom 'D') te polje na kojem se nalaze Slikar i tri mala ježa (označeno znakom 'S').
Slikar Paleta i tri mala ježa se u svakoj minuti mogu s polja na kojem se nalaze pomaknuti na 4 susjedna polja (gore, dolje, lijevo, desno). Svake minute se također i poplava proširi, i to tako da svako prazno polje koje je susjedno barem jednom već poplavljenom polju postaje poplavljeno. Ni voda, ni Slikar Paleta i tri mala ježa ne mogu proći kroz polje na kojem se nalazi stijena. Naravno, Slikar Paleta i tri mala ježa ne mogu proći kroz poplavljeno polje te voda ne može poplaviti Dabrovu kolibu.
Napišite program koji će za unesenu kartu Čudesne šume ispisati najkraće vrijeme potrebno da Slikar Paleta i tri mala ježa sigurno dođu do Dabrove kolibe.
Napomena: Slikar Paleta i tri mala ježa se ne smiju pomaknuti u polje koje će te minute biti poplavljeno.
U sljedećih R redaka nalazit će se po S znakova ('.', '*', 'X', 'D' i 'S'). U cijeloj karti nalazit će se točno jedan znak 'D' i točno jedan znak 'S'.
3 3
D.*
...
.S. Output:
33 3
D.*
...
..S Output:
KAKTUS 3 6
D...*.
.X.X..
....S. Output:
6Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.