7. vje~zbe iz C-a -- 2. zadatak
✓XHTML1
U koordinatnom sustavu zadano je nekoliko zidova. Oni su popisani u datoteci
"labirint.in", svaki u jednoj liniiji, i mogu biti oblika
- x1 x2 y
ili
| x y1 y2
. '-' ozna~cava horizontalan zid, koji se proteže od (x1,y) do (x2,y), dok '|' ozna~cava
vertikalan zid, koji se proteže od (x,y1) do (x,y2). Sve koordinate su cjelobrojne, izme~du
0 i 50.
Program treba:
- Pro~citati i ispravno parsirati datoteku labirint.in
- Popuniti matricu 51x51 nulama i jedinicama, ovisno o tome je li na
nekom mjestu zid ili nije
- Zatra~ziti od korisnika koordinate dviju to~caka: nazovimo ih start i cilj
- Provjeriti je li na nekom mjestu od njih zid -- ako jest, prekinuti
izvr~savanje uz poruku o gre~sci
- Pomo~tu breadth-first search algoritma
prona~ti je li mogu~te do~ti od starta do cilja
- Za 4. bod: nacrtati labirint, te najkra~ti mogu~ti put od starta do cilja.
Najkra~ti put nacrtajte funkcijom plline, drugom bojom nego labirint.
- Za 5. bod (te~sko!): Ako nije mogu~te do~ti od starta do cilja bez
prolaska kroz zidove, ispisati
koliko bi najmanje zidova trebalo sru~siti (preciznije, na koliko mjest~a)
za dolazak od starta do cilja
Queue mo~zete implementirati kako god ~zelite, vjerojatno je najlak~se
pomo~tu cirkularnog polja.
Ako vam je tako lak~se, smijete pretpostaviti da uvijek postoje sljede~ta 4 zida (okvir):
| 0 0 50
- 0 50 50
| 0 50 50
- 0 0 50
Opis breadth-first-search algoritma
- stavimo lokaciju starta na queue i ozna~cimo da je obi~dena (informaciju o tome da li je pojedina lokacija obi~dena ili ne pamtimo u matrici, mo~ze i istoj u kojoj pamtimo labirint)
- sve dok queue nije prazan:
- uzmemo lokaciju T s (po~cetka) queue-a i uklonimo ju s queue-a
- ukoliko je T cilj, prekidamo tra~zenje
- promotrimo redom lokacije neposredno iznad, ispod, lijevo i desno od T.
za svaku na kojoj se ne nalazi zid i koja nije jo~s obi~dena u~cinimo slijede~te:
- stavimo ju na kraj queue-a
- ozna~cimo da je obi~dena
Upute o tome kako na~ti najkra~ti put
Prilikom bfs algoritma, ne pamtimo samo je li neka lokacija obi~dena, ve~t koliko je koraka udaljena od starta. To je najjednostavnije učiniti ovako: start naravno ima udaljenost 0. Kad pokupimo T s početka queuea, ona ve~t ima neku udaljenost k -- zapamtimo je, i kad stavljamo neku od njenih susjedā na queue, zabilježimo da ima udaljenost k+1.
Jednom kad imamo udaljenosti, znamo koliko je cilj udaljen od starta (ako je uop~te mogu~te do~ti do njega), neka je to m. Sada crtamo unatrag: prva to~cka je cilj. Me~du njenim susjedima sigurno se nalazi neka to~cka s udaljeno~s~tu m-1: to je sljede~ta to~cka. Me~du susjedima te to~cke nalazi se neka s udaljeno~s~tu m-2 (to je tre~ta to~cka), i tako dalje. Koordinate tih to~caka (dok ne do~demo do starta) spremimo u dva polja, koja onda predamo funkciji plline s prvim parametrom m+1.