//#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;
}