|
|
Se consideră o matrice pătratică de ordinul "n" īn care avem o singura valoare nulă la o poziție cunoscută, mai multe valori -1 cu rol de valoare inaccesibilă și o valoare foarte mare īn restul locațiilor. Scopul este de a găsi cel mai mic drum de la valoarea 0 către o altă locație de asemenea cunoscută, diferită de locațiile inaccesibile. Algoritmul lui Lee marchează īn matrice pasul 1 peste tot īn jurul valorii 0 daca rămānem īn matrice și dacă nu se īntālnesc puncte inaccesibile. Se marchează cu pasul 2 īn jurul tuturor valorilor 1 in aceleași condiții ca īn pasul anterior. Aflāndu-ne la un pas oarecare k analizăm toți cei 4 vecini ai unei locații curente si marcăm cu pasul k+1, daca valoarea existentă īntr-un anumit vecin este : diferită de -1, rămāne īn matrice, memorează o valoare mai mare decat k+1, adică se optimizează traseul de la locația cu 0 către respectivul vecin.
#include<fstream>
#include<iostream>
#include<iomanip>
#define N 100
using namespace std;
void Lee(int a[][N],int m, int n, int l, int c, int pas)
{
if (l>1 && a[l-1][c]>pas+1)
{
a[l-1][c]=pas+1;
Lee(a,m,n,l-1,c,pas+1);
}
if (c<n && a[l][c+1]>pas+1)
{
a[l][c+1]=pas+1;
Lee(a,m,n,l,c+1,pas+1);
}
if (l<m && a[l+1][c]>pas+1)
{
a[l+1][c]=pas+1;
Lee(a,m,n,l+1,c,pas+1);
}
if (c>0 && a[l][c-1]>pas+1)
{
a[l][c-1]=pas+1;
Lee(a,m,n,l,c-1,pas+1);
}
}
void tipar (int a[][N], int m, int n)
{
int i,j;
for (i=1; i<=m; i++)
{
for (j=1; j<=n; j++)
cout<<setw(5)<<a[i][j];
cout<<endl;
}
}
int main ()
{
int a[N][N],l,c,lf,cf,m,n,i,j;
fstream f("Lee.txt",ios::in);
f>>m>>n;
for (i=1; i<=m; i++)
for (j=1; j<=n; j++)
{
f>>a[i][j];
if (a[i][j]==0)
{
l=i;
c=j;
}
}
cout<<"Dati lf si cf ";cin>>lf>>cf;
if (a[lf][cf]==-1)
return 0;
Lee(a,m,n,l,c,0);
if (a[lf][cf]==100)
cout<<"Locatie inaccesibila";
else
tipar(a,m,n);
}
Algoritmul prezentat folosește ca metodă principală recursivitatea.
_______________________________________
Ceva inteligent...
|
|
