Romeo și Julieta vor să se întâlnească în labirinticul oraș Verona. Cei doi trebuie să se vadă până apune soarele, de aceea au nevoie de ajutor pentru a stabili locul cel mai bun pentru întâlnire. Atât Romeo, cât și Julieta, se pot deplasa prin oraș din poziția curentă în oricare din cele 8 poziții învecinate (dacă harta le permite).
Orașul Verona este reprezentat printr-o hartă de n x m celule. Poziția de unde pleacă Romeo este reprezentat pe hartă prin literă R, iar cea a Julietei prin literă J. Zidurile orașului sunt reprezentate prin X (nu se poate trece prin acel loc din matrice). Zonele prin care pot trece sunt marcate cu spațiu.
Implementați folosind paradigma OOP un algoritm care să aleagă un punct de întâlnire în care atât Romeo, cât și Julieta, să poată ajunge în același timp plecând de acasă (același număr de pași), iar acest timp să fie minim.
Fișierul de intrare maze.in conține:
N M, care reprezintă numărul de linii și respectiv de coloane ale matricei, separate prin spațiu. 5 5 R XX X X X X XXX X X X X J X
Fișierul de ieșire maze.out va conține câte un răspuns pe linie, pentru fiecare soluţie găsită. Un răspuns este format din trei numere naturale separate prin câte un spațiu: t x y, având semnificația:
3 3 2
Pentru a-i reprezenta pe Romeo și Julieta vom avea o clasă Character care va avea următoarele informații:
Orașul va fi reprezentat de clasa CityMap (numele Map este luat deja) care va conține:
Determinarea poziției de întâlnire cu cel mai mic cost, cât și efortul depus de fiecare personaj se vor implementa în clasa Game. Această pornește de la următoarea structură:
play() care va implementa algoritmul de găsire a punctului de întâlnire. Nu uitați de paginile wiki: indicatii pentru teme și coding style.
Arhiva pe care o veţi urca pe Vmchecker va trebui să conţină în directorul rădăcină:
src, inclusivdoc, generat de javadocREADME cu descrierea implementării