PROBLEME BACKTRACKING

IN PLAN

 

1.     Sa se completeze o tabla de 5*5 cu saritura calului.

Iata doua solutii:

 

1

14

9

20

3

24

19

2

15

10

13

8

25

4

21

18

23

6

11

16

7

12

17

22

5

1

14

9

20

3

24

19

2

15

10

13

8

23

4

21

18

25

6

11

16

7

12

17

22

5

 

Aflati numarul de solutii si afisati tablele.

 

         2.Se da un tablou bidimensional (m linii, n coloane si m*n componente) cu elemente distincte. Se dau si coordonatele primului punct. Ss se genereze un traseu in matrice pornind de la punctul dat astfel incat suma ∑ k*a[i][j]  (unde k=1 → n*m ) sa fie maxima. In matrice se poate avansa numai la elemente vecine (pe cele 8 directii).

Ex: n=m=4;pozitia initiala : linia 3,coloana 2;

 

13

14

3

4

12

2

15

5

11

1

16

6

10

9

8

7

 Suma maxima va fi: 1*1+2*2+3*3+…+16*16.

 

         3.Ali Baba

Ali Baba i-a surprins pe cei 40 de hoti, in timp ce cotrobaiau printre comorile lui. Hotii erau multi, el era singur, asa ca a incercat sa negocieze cu ei. Avea o ladita speciala, pe care era notat numarul de diamante aflate in aceasta, un numar avnd cel mult 40 de cifre, intr-o baza b. Ali Baba a propus conducatorului hotilor sa elimine din numar b cifre, dupa care poate sa plece cu atatea diamante cate reprezinta numarul ramas.

Hotul, mai intai a stabilit valoarea cea mai mica  posibila b, deoarece a vrut sa stabileasca un numar cat mai mic posibil de cifre pe care urmeaza sa le elimine. Apoi a inceput tierea cifrelor. In timpul eliminarii a urmarit ca numarul ramas sa fie cat se poate de mare.

Scrieti un program care il ajuta pe hot(Ali Baba are destule comori…).

 

Date de intrare

Pe prima linie a fisierului de intrare ALIBABA.IN se afla un sir de cifre, nedespartite prin spatii.

 

Date de iesire

Pe prima linie a fisierului de iesire ALIBABA.OUT  se va scrie pe fiecare cate un numar, reprezentand numasrul ramas dupa eliminarea unei cifre.

 

Restrictii si precizari

2<=b<=10

 

Exemplu

ALIBABA.IN

323332112   

 

ALIBABA.OUT

4

33332112

333212

33322

3332  

 

            Un labirint dreptunghiular cu m linii si n coloane contine culoare (reprezentate prin 0) si pereti (reprezentati prin 1). Se dau coordonatele initiale ale unui soricel si coordonatele finale , unde trebuie sa ajunga.  Soricelul poate avansa sus, jos , stanga sau dreapta.(Incercati si cu cele 8 directii)

1.         Sa se genereze toate solutiile.

2.         Sa se afiseze soultia cea mai lunga (scurta)

 

            Un labirint dreptunghiular cu m linii si n coloane contine culoare (reprezentate prin 0) si pereti (reprezentati prin 1). Se dau coordonatele initiale ale unui soricel care trebuie sa iasa din labirint.SA se genereze toate solutiile

 

            Un labirint dreptunghiular cu m linii si n coloane contine culoare (reprezentate prin 0) si pereti (reprezentati prin -1). Se dau coordonatele initiale ale unui soricel si coordonatele finale , unde trebuie sa ajunga.  Pe culoare se gasesc bucati de branza pt care se cunoaste greutatea in grame.

1.         Sa se genereze toate solutiile., pt fiecare se afiseaza cantitatea consumata

2.         Sa se afiseze soultia cea mai „consistenta”

 

            Un broscoi se gaseste pe o frunza de nufar pe un lac. Broscoiul poate sari numai sub forma sariturii calului si nu trebuie sa cada in apa. Pe lac se gasesc mai multe frunze. Se da dimensiunea lacului (ca matrice mxn) si coordonatele frunzelor. Ajutati-l pe roscoi sa iasa din lac. (si alte variante: de la o frunza la alta etc)

 

            Problema fotografiei-