//#define MAX 50;#include <iostream.h>#include <conio.h>void delete_isolated(int a[7][7],int n) //pun 0 pe pozitiile cu 1 izolat{ for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (a[i][j]==1 && a[i-1][j]==0 && a[i+1][j]==0 && a[i][j-1]==0 && a[i][j+1]==0) a[i][j]=0;}void init_matrix(int a[7][7],int n){ for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j]=0;}void bktr(int i,int j,int a[7][7],int b[7][7],int &s,int n,int i2,int j2){ if (i>1 && b[i-1][j]!=1 && a[i-1][j]!=0)//mutare o linie mai sus, coloana ramane la fel { b[i-1][j]=1; if (i-1==i2 && j==j2) { s++; init_matrix(b,7); } bktr(i-1,j,a,b,s,n,i2,j2); } if (i<=n-1 && b[i+1][j]!=1 && a[i+1][j]!=0)//mutare o linie mai jos, coloana ramane la fel { b[i+1][j]=1; if (i+1==i2 && j==j2) { s++; init_matrix(b,7); } bktr(i+1,j,a,b,s,n,i2,j2); } if (j>1 && b[i][j-1]!=1 && a[i][j-1]!=0)//mutare o coloana la stanga, pe aceeasi linie { b[i][j-1]=1; if (i==i2 && j-1==j2) { s++; init_matrix(b,7); } bktr(i,j-1,a,b,s,n,i2,j2); } if (j<=n-1 && b[i][j+1]!=1 && a[i][j+1]!=0)//mutare o coloana la dreapta, pe aceeasi linie { b[i][j+1]=s; if (i==i2 && j+1==j2) { s++; init_matrix(b,7); } bktr(i,j+1,a,b,s,n,i2,j2); }}int main(){ int a[7][7];int b[7][7]; int i,j,n,last,curr,i1,i2,j1,j2,s; init_matrix(a,7); init_matrix(b,7); cout<<"Introduceti nodurile grafului:"<<endl; cin>>last;cin>>curr;n=0; do { a[last][curr]=1; n=(last<curr) ? curr:last; cin>>last; cin>>curr; }while (last!=0 && curr!=0); cout<<"Introduceti cele 2 noduri: "<<endl; cin>>i1>>j1>>i2>>j2; s=0; delete_isolated(a,n); bktr(i1,j1,a,b,s,n,i2,j2); cout<<s<<endl; getch(); return 0;}