Backtracking – problema labirintului

Se dă un labirint reprezentat sub forma unei matrici cu n linii şi m coloane, conţinând doar valori 0 şi 1. O succesiune de 1 reprezintă un drum iar o reprezintă zid. Dintr-un punct iniţial, a cărui coordonate se citesc, porneşte o persoană. Să se afişeze toate posibilităţile ca acea persoană să iasă din labirint (să atingă una din marginile matricei), ştiind că deplasarea se poate face doar prin valori 1 ale matricei, iar salturile se pot face în stânga, dreapta, jos şi sus.


#include "stdio.h"
#include "conio.h"
//matricea a conţine valorile labirintului iar în matricea rez vom păstra drumul
//parcurs în cadrul unei posibile soluţii
int a[10][10],rez[10][10],n;
void scrie(void)
{
  int i,j;
  for(i=0;i < n;i++)   {     //afişăm matricea drumului de ieşire; succesiunea de 1 reprezintă drumul     for(j=0;j < n;j++)     printf("%d",rez[i][j]);     putchar("\n");   }   putchar("\n");   //după fiecare soluţie se aşteaptă apăsarea unei taste   getch(); }

void labirint(int x, int y)
{
  //dacă am atins una din marginile matricei
  if((x==0) || (x==n-1) || (y==0) || (y==n-1))
  {
    //marcăm punctul de margine ca vizitat
    rez[x][y]=1;
    //apelăm funcţia de afişare
    scrie();
  }
  else
  //în cazul în care nu suntem pe margine
  {
    //încercăm direcţia 1 din figura de mai sus; rez trebuie să conţină
    //valoarea 0 (în cadrul drumului curent să nu fi sărit în acest nou
    //punct) iar în matricea labirint să avem drum (adică valoarea 1)
    if((x+1 < n)&&(rez[x+1][y]==0)&&(a[x+1][y]==1))     {       //marcăm vizitat punctul în care am sărit       rez[x+1][y]=1;       //apelăm funcţia minge pornind de la acest nou punct       labirint(x+1,y);       //la revenire din backtracking punem din nou valoarea       // o în matricea drumului       rez[x+1][y]=0;     }     //încercăm direcţia 2     if((y-1 >= 0)&&(rez[x][y-1] == 0)&&(a[x][y-1]==1))
    {
      rez[x][y-1]=1;
      labirint(x,y-1);
      rez[x][y-1]=0;
    }
    //încercăm direcţia 3
    if((x-1 i>= 0)&&(rez[x-1][y] == 0)&&(a[x-1][y] == 1))
    {
      rez[x-1][y]=1;
      labirint (x-1,y);
      rez[x-1][y]=0;
    }
    //încercăm direcţia 4
    if((y+1 < n)&&(rez[x][y+1] == 0)&&(a[x][y+1]==1))     {     rez[x][y+1]=1;     labirint(x,y+1);     rez[x][y+1]=0;     }   } } void main(void) {   int i,j,xi,yi;   printf("Introdu dimensiunea matricii:");   scanf("%d",&n);   printf("Introdu valorile matricii labirint\n");   for(i=0;i < n;i++)     for(j=0;j < n;j++)     {       printf("a[%d][%d]=",i,j);       //se citeşte 1 pentru drum şi 0 pentru zid       scanf("%d",&a[i][j]);       //iniţializăm cu o matricea drumului       rez[i][j]=0;     }   printf("Introdu linia de pornire:");   scanf("%d",&xi);   printf("Introdu coloana de pornire:");   scanf("%d",&yi);   //drumul începe din punctul iniţial   rez[xi][yi]=1;   //apelăm funcţia recursivă labirint pornind din punctul iniţial   labirint(xi,yi); }

Leave a Reply

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

10 − 7 =

Time limit is exhausted. Please reload CAPTCHA.