Distante!

[•chera_lary]

Buna ziua!
Doresc sa stiu cum pot determina lungimea minima dintre doua puncte ale unei matrice tinand cont ca nu te poti deplasa pe diagonala matricei (bidimensionala).
Ex matrice:
1 2 3
4 5 6
7 8 9
Distanta minima din coltul din stanga-sus pana in coltul din dreapta-jos este 21 : 1 -> 2 -> 3 ->6->9
Va multumesc !

[•Cosmin]

Poti folosi orice algoritm de cautare de drumuri minime.

[•devilkind]

pe ex tau distanta minima nu e 21?? 1 - 2 - 3 - 6 - 9

[•sigrid]

Ba da  .

Poti folosi algoritmul lui lee. Daca nu stii cu ce se mananca ai aici un articol: http://www.ginfo.ro/revista/15_2/focus1.pdf

Spor.

[•devilkind]

nu poti folosi lee deoarece ai costuri. Poti folosi algoritmul lui Djikstra in schimb.

[•chera_lary]

Va multumesc pentru ajutor!
Intradevar, distanata minima este 1 -> 2 -> 3 -> 6 -> 9 ! Imi cer scuze pentru greseala facuta 

[•sima_cotizo]

nu poti folosi lee deoarece ai costuri. Poti folosi algoritmul lui Djikstra in schimb.

popular tot "lee" ii zice

[•Marius]

nu poti folosi lee deoarece ai costuri. Poti folosi algoritmul lui Djikstra in schimb.

În cazul în care ai cost pe noduri poţi folosi o coadă simplă. Şi cred că se numeşte Lee, deşi văd că nu e mare diferenţă de Bellman Ford cu coadă.

Nu prea e pe SGU problema...

[•sigrid]

Nu conteaza asa mult cum se numeste  .

Algoritmul este interesant pentru un incepator.
Laurentiu ai reusit sa rezolvi problema?

[•chera_lary]

Da, am reusit sa rezolv problema!
Va multumesc pentru ajutorul acordat, si pentru ca v-ati implicat!

[•Marius]

În primul rând felicitări. În al doilea rând, ai grijă unde postezi data viitoare.

Iată ce ai pe prima pagină din Index:

Informatica
Informatica, algoritmi, structuri de date, matematica... stii tu

[•chera_lary]

Am reusit urmatoarea implementare :
Matrice :
10 3
1 2 5
1 3 1
0 8 1
10 = suma de bani avuta initial;
n = 3;
Programul afiseaza suma maxima de bani ramasa angajatului dupa ce traverseaza firma de la un birou la altul (1 - stanga sus; la 1-dreapta jos);

Cod:

/*Taxe*/
#include <stdio.h>
#define fin "taxe.in"
#define fout "taxe.out"

int n,s;
long int taxa[10][10];
long int taxaMin[10][10];
long int infinit=1000;

void citeste();
void drum();
int minTaxeVecini(int,int);
int minim(int,int);
void tipar();

void init(){
	for(int i=0;i<=n+1;++i)
	  for(int j=0;j<=n+1;++j)
	    taxaMin[i][j]=infinit;
	taxaMin[1][1]=taxa[1][1];
}

void main(){
	citeste();
	init();
        tipar();
	drum();
	tipar();
}

void citeste(){
	FILE *f=fopen(fin,"rt");
	fscanf(f,"%d %d\n",&s,&n);
	for(int i=1;i<=n;++i)
	  for(int j=1;j<=n;++j)
	    fscanf(f,"%d",&taxa[i][j]);
        fclose(f);
}

void drum(){
	int i,j,min;
	int amOptimizare;

	amOptimizare=1;
	while(amOptimizare){
	  amOptimizare=0;
	  for(int i=1;i<=n;++i)
	    for(int j=1;j<=n;++j){
	      min=minTaxeVecini(i,j);
	      if(min+taxa[i][j]<taxaMin[i][j]){
		taxaMin[i][j]=min+taxa[i][j];
                amOptimizare=1;
	      }
	    }
	}
	if(taxaMin[n][n]<=s)
	  printf("%d\n",s-taxaMin[n][n]);
	else
	  printf("%d\n",-1);
}

int minTaxeVecini(int i, int j){
	int min1,min2;
	min1=minim(taxaMin[i-1][j],taxaMin[i+1][j]);
        min2=minim(taxaMin[i][j-1],taxaMin[i][j+1]);
        return minim(min1,min2);
}

int minim(int a, int b){
	if(a>b) return b;
	else return a;
}

void tipar(){
	for(int i=1;i<=n;++i){
	  for(int j=1;j<=n;++j)
	    printf("%d ",taxaMin[i][j]);
	  printf("\n");
	}
        printf("\n");
}

[•Marius]

E corect algoritmul. Dacă iterai while()ul de N² ori obţineai acelaşi rezultat. Algoritmul se numeşte Bellman Ford. Dar dacă iterezi cât timp mai poţi relaxa, atunci ai o optimizare. Complexitatea lui e O(N⁴).

Cu algoritmul lui Dijkstra de drumuri minime, poţi obţine complexitatea O(N² logN²). Mult mai eficient.

[•Dastas]

Problema nu merge si cu memoizare?

Fie f(i, j) costul minim pentru a ajunge de la punctul de plecare (x, y) pana in (i, j). f(i, j) = cost[ i ][ j ] + min(f(i+1, j), f(i, j+1), f(i-1, j), f(i, j-1)).

f(x, y) se initializeaza cu cost[ x ][ y ] si eventual mai trebuie avut grija sa nu se apeleze recursiv pentru zone inaccesibile (i, j < 0 etc)

Pare corect. Complexitatea nu ar fi patratica daca se aplica memoizare?

[•chera_lary]

Metoda pe care ai prezentat-o nu are o eroare? De exemplu:
In matricea,
1 2 5
1 3 1
0 8 1
, algoritmul cand va ajunge in nodul (1,0), nu o sa aleaga intre 3 si 0 pe 0   , nodul (2,0) al matricei. In cazul in care va alege nodul (2,0) programul va afisa un rezultat eronat, deoarece drumul minim este : 1->1->3->1->1 si nu 1->1->0->8->1 !

[•Dastas]

Tu ai ales minimul dintre valori ale matricii costurilor. Eu am zis ca se alege minimul dintre apeluri recursive.

Uite un program care l-am scris rapid, nu stiu daca e 100% corect, dar pe exemplul tau da corect: 7.

Cod:

int n, m;
int a[maxn][maxn];
int memo[maxn][maxn];
int v[maxn][maxn];

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int back[maxn][maxn];

int go(int x, int y)
{
    if ( memo[x][y] != -1 )
        return memo[x][y];

    if ( v[x][y] )
        return 1 << 29;

    v[x][y] = 1;

    for ( int i = 0; i < 4; ++i )
    {
        int X = x + dx[i];
        int Y = y + dy[i];

        if ( X > 0 && Y > 0 && X <= n && Y <= m )
            if ( go(X, Y) + a[x][y] < memo[x][y] || memo[x][y] == -1 )
                memo[x][y] = go(X, Y) + a[x][y], back[x][y] = i;
    }

    v[x][y] = 0;

    return memo[x][y];
}

int main ()
{
    fscanf(in, "%d %d", &n, &m);

    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
            fscanf(in, "%d", &a[i][j]), memo[i][j] = -1;

    memo[1][1] = a[1][1];

    printf("%d\n", go(3, 3));

    for ( int i = 1; i <= n; ++i )
    {
        for ( int j = 1; j <= m; ++j )
            printf("%d ", back[i][j]);
        printf("\n");
    }

    return 0;
}