/*1. Intr-o camera cu  dale patrate se afla o maimuta si nb banane.Numarul bananelor,
 pozitia maimutei si pozitiile bananelorse citesc de la tastatura..
Maimuta se poate deplasa in fiecare din cele opt pozitii vecine.
Energia consumata este egala cu cu o unitate la deplasarea ortogonala , respectiv 1.41
unitati pentru deplasarea pe diagonala.
Se cere traseul opim si energia totala consumata de maimuta pentru a ajunge la toate bananele.
Traseul optim este identificat printr-o energie consumata minima.
Exemplu: Daca dimensiunea camerei este 3x4 , nb=4, pozitiile bananelor sunt (1,2) (2,1) (3,2) (3,4)
, iar pozitia  initiala a maimutei  (1,4), atunci un traseu este : (1,4), (1,3).(1,2),(2,1),(3,2),(3,3),(3,4)
iar energia consumata este 6.82
*/

#include<iostream.h>
int a[100][100], n, m,b[100][100], dx[8]={-1,-1,-1,0,0,1,1,1}, dy[8]={-1,0,1,-1,1,-1,0,1}, nb, x,y, z[100][100],k=0;
float min=100;
float e;
float en[8]={1.41,1,1.41,1,1,1.41,1,1.41};

void citire(int &n, int &m, int &nb, int a[100][100])
{
 int x,y;
 cout<<"dati dimensiunile matricei : ";
 cin>>n>>m;
 cout<<"nr bananelor: ";
 cin>>nb;
 cout<<"dati pozitiile bananelor: ";
 for(int i=1;i<=nb;i++)
  {
   cin>>x>>y;
   a[x][y]=1;
  }
 
}

float minim(int n,int m, int b[100][100])
{
 if(e<min)
 {
  min=e;
  for(int i=1;i<=n;i++)
   for(int j=1;j<=m;j++)
    z[i][j]=b[i][j];
 }
}


void back(int x1, int y1, int p, int k)
{
 int xx,yy;
 for(int i=0;i<=7;i++)
  {
   xx=x1+dx[i];
   yy=y1+dy[i];
   
   if(xx>=1 &&xx<=n && yy>=1 && yy<=m && b[xx][yy]==0)
   {
    b[xx][yy]=p+1;e=e+en[i];
    if(a[xx][yy]==1)k++;
   
	if(k==nb) minim(n,m,b);
          else back(xx,yy,p+1,k);
   b[xx][yy]=0;
   e=e-en[i];
   if(a[xx][yy]==1)k--;
   
   }
  }
}

 

main()
{
 citire(n,m,nb,a);
 cout<<"pozitia  maimutei : ";
 cin>>x>>y;
 b[x][y]=1;
 back(x,y,1,0);
 
 for(int i=1;i<=n;i++)
  {for(int j=1;j<=m;j++)
   cout<<z[i][j]<<" ";
  cout<<endl;
  }
 cout<<endl<<"energia consumata: "<<min;
}