Imprimă pagina - Algoritm Lee Clasic Coada

Titlul: Algoritm Lee Clasic Coada
Scris de: George Popoiu din Iulie 14, 2009, 12:33:42

Am dat peste o problema la care se spunea ca se rezolva folosind Lee clasic cu o Coada.

Am cautat pe google ceva teorie dar nu prea am gasit, daca aveti vreun link sau stiti algoritmul si vreti sa mi-l explicati as fi mai mult decat recunoscator :D :wink:

Multumesc Anticipat !!!

Titlul: Răspuns: Algoritm Lee Clasic Coada
Scris de: Cezar Mocan din Iulie 14, 2009, 14:07:14

"Lee clasic cu coada" inseamna de fapt o parcurgere in latime a unei matrici. Daca nu stii parcurgere in latime uita-te peste problema (http://infoarena.ro/problema/bfs) din Arhiva Educationala. Spor!

Titlul: RÄƒspuns: Algoritm Lee Clasic Coada
Scris de: alexandru din August 07, 2009, 07:52:34

Lee sau un BFS, e chiar usor de facut:
1. alegi un varf de plecare ( in general 1 )
2. pui varful in coada
3. cat timp coada nu este vida
4. extragi primul element.
5. determini toti vecini lui x care nu au fost vizitati si ii pui in coada, marcandui ca vizitati :)
6. revi la pasul 3
5. continuie programul cu ce trebuie ;)
Implementarea, o sa folosesc putin stl pentru rapiditate

Cod:

#include <fstream>
#include <queue>  //pentru coada
#include <bitset> // pentru a retine matricea de adiacenta avem nevoie doar de o matrice de biti ( 1 sau 0 )
#define Nmax 301
using namespace std;
ifstream in;
ofstream out;
bitset<Nmax> v[Nmax], uz; //in v - retin matricea de adiacenta si in uz ce varf a fost vizitat
queue<int> Q; //coada 
int main()
{int N,M,x,y,i;
    in.open("lee.in");;
    in>>N>>M; // N - numarul de varfuri , M- numarul de muchii
    while( M -- )  
    {
              in>>x>>y;  
             v[x].flip(y); v[y].flip(x);  //marchez v[x][y]=v[y][x]=1
    }
    Q.push(1); // inserez 1 in coada 
    uz.flip(1);
    out.open("lee.out");
    while( !Q.empty() ) //3
    {
              x=Q.front(); Q.pop(); //4
              for( i=1; i<=N; ++i )  //5
                 if( v[x][i] && !uz[i] )
                 {
                         Q.push(i); uz.flip(i);
                 }
    }
     //restul programului
     return 0;
}

Sper ca fost de ajutor ;)

Titlul: RÄƒspuns: Algoritm Lee Clasic Coada
Scris de: Cara Sabina din Februarie 08, 2012, 22:44:27

si eu am o problema, plec dintr-un punct si tre' sa ajung in altul. nu prea reusesc. iau o matr viz si pun 1 cand am trecut pe acolo, dar nu stiu cum sa adun in matricea data astfel incat sa fac suma maxima pe cel mai scurt drum pentru a iesi din matrice

Cod:

int Lee()
{
    struct coord{
        int x, y;
    } c[101*101];

    c[0].x = si;
    c[0].y = sj;
    a[si][sj] = 0;//nu stiu ce val sa pun
    viz[si][sj] = 1;//am vizitat 
    int p=0,u=0;
    while(p<=u)
    {
        int x1 = c[p].x;
        int y1 = c[p].y;
        for(int k = 0;k<4;k++)
        {
            int xv = x1 + dx[k];
            int yv = y1 + dy[k];
            if(a[xv][yv] > a[x1][y1] && viz[xv][yv] == 0)
                {
                    u++;
                    c[u].x = xv;
                    c[u].y = yv;
                    a[xv][yv] += a[x1][y1];
                }
        }
        cout<<x1<<" "<<y1<<endl;
        if (x1== -1 && y1 == -1)
            return -2;
        p++;
    }
    return -1;
}

ma ajuta orice indicatie.inca nu am clar procedeul de rezolvare, ce sa fac in matricea initiala?

Multumesc anticipat!

Editat de admin: Foloseste tagul "code" cand postezi surse.

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: George Popoiu din Iulie 14, 2009, 12:33:42