From b7e6d71ef8ff501761693f0f46fef9ce0b86fc8c Mon Sep 17 00:00:00 2001 From: Doni Pracner Date: Tue, 29 Nov 2016 22:06:52 +0100 Subject: [PATCH] Lavirint, postojanje puta, doteran tekst zadatka --- .../PostojanjePuta/zad-put-u-lavirintu.txt | 30 ++++++++++--------- 1 file changed, 16 insertions(+), 14 deletions(-) diff --git a/PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/zad-put-u-lavirintu.txt b/PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/zad-put-u-lavirintu.txt index 66bec95..7639948 100644 --- a/PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/zad-put-u-lavirintu.txt +++ b/PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/zad-put-u-lavirintu.txt @@ -53,25 +53,21 @@ Modifikacije su opisane na kraju teksta. Zadatak ============================================================ -Napisati klasu LavirintProgram koja ucitava ime fajla u kojem -se nalazi definisan lavirint, koordinate pocetne pozicije -(x, y) od koje se trazi izlaz iz lavirinta, kao i izbor sta -zelimo da radimo. Nakon ucitanog izbora, klasa treba da ucita -lavirint iz datog fajla, ispise ga na ekran i izvrsi izabranu -operaciju. +Napisati klasu PostojanjePuta koja ucitava ime fajla u kojem +se nalazi definisan lavirint. Program treba da ucita +lavirint iz datog fajla, ispise ga na ekran i proveri +postojanje puta. -Ponuditi korisniku sledeci izbor: -1 - provera da li postoji put od unetog polja do izlaza -2 - ispis puta ukoliko postoji, odnosno ispis poruke da put - ne postoji +Uzeti da je pocetno polje uvek 0,0, odnosno gornji levi +ugao. Pretrazivanje sa vracanjem ------------------------------------------------------------ -Jedan od nacina da se uradi zadatak je koriscenjem pretrazivanja -sa vracanjem (poznatom u literaturi pod engleskim nazivom -"backtrack"). +Jedan od nacina da se uradi zadatak je koriscenjem +pretrazivanja sa vracanjem (poznatom u literaturi pod +engleskim nazivom "backtrack"). Ideja je jednostavna, krenemo od prvog polja, oznacimo ga kao poseceno i pokusamo da se prebacimo na bilo koje @@ -89,7 +85,6 @@ Backtrack je najlakse izvoditi rekurzivno, tako da se poziv procedure vrsi za pojedinacno polje. Ovako se povratkom iz rekurzije vracamo na polje odakle smo dosli. - Jedna od mogucih varijanti ideje procedure: rek(i,j,...) @@ -110,6 +105,13 @@ rek(i,j,...) Prosirenje zadatka: ------------------------------------------------------------ +Dodati da se korisnik pita za pocetno polje u lavirintu +umesto da se uvek koristi 0,0. + +Dodati da se ispise nadjeni put u lavirintu (u sustini je +dosta pri povratku iz rekurzije ispisivati polja koja +su vratila true). + Neka je dat lavirint sa sledecim dodatnim poljima: -1 = rupa na putu bilo koji pozitivan broj = visina prepreke na putu -- 2.17.1