Backtracking – problema mingii

Se dă un teren parcelat cu porţiuni de teren pătrate, fiecare având o anumită cotă. Cotele se citesc de la tastatură şi se reţin într-o matrice de m/n poziţii. O bilă se găseşte într-o poziţie iniţială, având nişte coordonate iniţiale ce se citesc de la tastatură. Se ştie că bila poate sări de la o cotă mai mare spre o cotă mai mică, pe orizontală, verticală şi pe diagonale, rostogolindu-se astfel către marginea terenului. Se cere să se afişeze toate variantele de deplasare a mingii până la atingerea unei margini.


#include "stdio.h"
#include "conio.h"
int a[8]={1,1,0,-1,-1,-1,0,1}, b[8]={0,1,1,1,0,-1,-1,-1};
//tablou va păstra cotele iar drum drumul
//parcurs de minge (folosind valori 0 şi 1)
int tablou[10][10],drum[10][10],m,n;
//funcţia de afişare a soluţiei void afiseaza(void)
{
  int p,r;
  for(p=0;p < m;p++)   {   for(r=0;r < n;r++)     printf("%d",drum[p][r]);   putchar("\n");   }   putchar("\n");   getch(); }
void minge(int i, int j)
{
  int i1,j1,d;
  //dacă am ajuns la una din margini
  if((i == 0) || (i == m-1) || (j == 0) || (j == n-1))
  {
    //afişăm soluţia
    afiseaza();
    //pentru că ne întoarcem din backtracking refacem
    //valoarea 0 în matricea drumului
    drum[i][j]=0;
  }
  //pentru ultimul element din drum
  else
    //dacă nu ne găsim pe vreuna din margini
    for(d=0;d < 8;d++)     //încercăm fiecare din cele 8 posibilităţi de salt     {       //i1 este linia în care încercăm să sărim       i1=i+a[d];       //j1 este coloana în care încercăm să sărim       j1=j+b[d];       //dacă noile coordonate se încadrează în matrice, noua valoare este       //mai mică decât precdenta (cerinţă pentru salt şi în noul punct       //nu am sărit în actualul drum atunci       if((i1 < m)&&(j1 < n)&&(i1 >= 0)&&(j1 >= 0)&&(tablou[i1][j1] < tablou[i][j])&&(!drum[i1][j1]))       {         //marcăm în drum noul punct în care am sărit         drum[i1][j1]=1;         //apelăm funcţia recursivă pornind din noul punct         minge(i1,j1);         //la întoarcere vom repune valoarea o în matricea drumurilor         drum[i1]|j1]=0;       }     }     //se închide instrucţiunea for     //nu am mai găsit drum din (i,j) deci repune pe o poziţia     //corespunzătoare din matricea drumurilor     drum[i][j]=0; } void main(void) {   int i,j,xi,yi;   printf("Introdu nr de linii:");   scanf("%d",&m);   printf("Introdu nr de coloane:");   scanf("%d",&n);   printf("Introdu cotele:\n");   for(i=0;i < m;i++)     for(j=0;j < n;j++)     {       //drum va conţine drumul format către ieşire       drum[i][j]=0;       //tablou va conţine cotele       printf("tablou[%d][%d]=",i,j);       scanf("%d",&tablou[i][j]);     }   printf("Introdu linia de pornire:");   scanf("%d",&xi);   printf("Introud coloana de pornire:");   scanf("%d",&yi);   //marcăm în drum punctul de pornire   drum[xi][yi]=1;   //apelăm funcţia recursivă pornind din punctul iniţial   minge(xi,yi); }

Leave a Reply

Your email address will not be published. Required fields are marked *

1 × 5 =

Time limit is exhausted. Please reload CAPTCHA.