BFS

Može li mi netko objasniti bfs.

Evo pogledaj ovaj fajl .

http://www.dms.rs/agogeit/data/dodatne_2009/Osnovni grafovski algoritmi A [teorija].pdf

Tu su ti date neke osnove iz teorije grafova, ako ti i dalje ne bude bilo jasno pitaj . ;-)

Imaš li za c++?

Ja ću napisati kod :D

void bfs() {
     while (!Q.empty()) {
           koord pos = Q.front();
           Q.pop();
           for (int i = 0 ; i < 4 ; ++i) {
               koord dalje = koord (dx[ i ] + pos.x, dy[ i ] + pos.y);
               if (dalje.x < 0 || dalje.x >= n || dalje.y < 0 || dalje.y >= m) continue;
               if (x[ dalje.x ][ dalje.y ] == '#') continue; //x je polje koje sam učitao
               if (!bio[ dalje.x ][ dalje.y ]) {
                  bio[ dalje.x ][ dalje.y ] = true;
                  dist[ dalj.x ][ dalje.y ] = dist[ pos.x ][ pos.y ] + 1;
                  Q.push(dalje);
               }
           }
     }
}

Na početku možeš imati void bfs ( int a, int b )
i onda prije whilea Q.push( koord ( a, b ) ).
To ti govori na kojoj poziciji trenutno počinješ.
Onda imam for do 4 jer se većinom u zadatcima možeš kretati u 4 glavna smjera.
Dalje imaš uvjete ako izlazi iz okvira matrice ili je neki znak na koji nesmije stat onda continue ( nastavi a da ne gledaš ostatak funkcije ).
I na kraju imaš poseban if ( !bio[ dalje.x ][ dalje.y ] ) .
To znači ako nije bio na tom polju tada odi na to polje.
izračunaj udaljenost i ubaci dalje u Q.

Onda da ti objasnim ovaj red:

koord dalje = koord ( pos.x + dx[ i ], pos.y + dy[ i ] )

.
tu imaš strukturu:

struct koord {
int x, y;
koord ( int _x = 0, int _y = 0  ) {
x = _x;
y = _y;
}
};

Nadam se da si skužio što to radi. Ako ne, taj red ti postavlja novi dalje.x i dalje.y tj. pomiče ga na mjesta gdje glavni lik zadatka mora ići.

E i na kraju svega ovoga:
BFS ti je inače ubacivanje u queue.
Znači za kodiranje BFS-a ti treba
#include <queue> i queue< koord > ili ako ti želiš, možeš koristiti queue< pair< int, int > > mada je meni lakši onaj prvi način.

Nadam se da si skužio, ako nešto nije jasno postavi pitanje.

pozz, Kinky

Postavi rješenje ovog zadatka:
A B-dimenzije
D-početna pozicija
C-cesta
S-suma
I-izvor
Dario želi doći do izvora, a smije ići samo po cesti.
Ulaz:
4 3
DSI
CCC
CSC
CCC
Izlaz:4

Pa sa BFS-om!

Mogu li vidjeti kod.

Evo

#include <cstdio>
#include <queue>

using namespace std;

struct koord {
       int x, y;
       koord ( int _x = 0, int _y = 0 ) {
             x = _x;
             y = _y;
       }
};

queue< koord > Q;
//4.osnovna smjera
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int N, M;
char polje[ 101 ][ 101 ];
int dist[ 101 ][ 101 ];
bool bio[ 101 ][ 101 ];
int pocx, pocy;
int endx, endy;

void bfs ( int a, int b ) {
     Q.push ( koord ( a, b ) );
     while ( ! Q.empty() ) {
           koord pos = Q.front();
           Q.pop();
           for ( int i = 0 ; i < 4 ; ++i ) {
               koord dalje = koord ( pos.x + dx[ i ], pos.y + dy[ i ] );
               if ( dalje.x < 0 || dalje.x >= N || dalje.y < 0 || dalje.y >= M ) {
                  continue;
               }
               if ( polje[ dalje.x ][ dalje.y ] == 'S' ) {
                  continue;
               }
               if ( !bio[ dalje.x ][ dalje.y ] ) {
                  bio[ dalje.x ][ dalje.y ] = 1;
                  dist[ dalje.x ][ dalje.y ] = dist[ pos.x ][ pos.y ] + 1;
                  Q.push ( dalje );
               }
           }
     }
}

int main() {
    scanf ( "%d %d", &N, &M );
    for ( int i = 0 ; i < N ; ++i ) {
        scanf ( "%s", polje[ i ] );
    }
    for ( int i = 0 ; i < N ; ++i ) {
        for ( int j = 0; j < M ; ++j ) {
            if ( polje[ i ][ j ] == 'D' ) {
               pocx = i;
               pocy = j;
            }
            if ( polje[ i ][ j ] == 'I' ) {
               endx = i;
               endy = j;
            }
        }
    }
    bfs ( pocx, pocy );
    printf ( "%d\n", dist[ endx ][ endy ] );
return 0;
}

Hvala puno.

Prvo sam mislio da ti dam samo BFS, ali sam pomislio da na z-treningu možda bude još ljudi koji možda ne kuže pa sam stavio cijeli kod.
Ako želiš mogu pobrisat!

Ostavi da drugi mogu vidjeti.

OK, ako netko ima neku primjedbu neka napiše!!!

pozz, Kinky ;-)

Pozz DSA :-)

A ako može biti 8 smjerova i koso

Prosiris dx[] i dy[] i ne ides do 4 nego do 8 ...