C++, optimalna putanja (BFS)

Koristimo strukturu Q u C++.

imamo bio[Max_row][Max_col], sve postavimo na -1 to znaci da nismo nikada bili.

queue < pair < int, int > > Q;

tako inicijaliziramo Q. u koji spremamo uredjeni par brojeva tj. koordinate.

postoje 4 poteza.

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

const int dy[4] = { 0, -1, 0, 1 }

bio[start_x][start_y] = 0;

Q.push( make_pair( start_x, start_y ) );

while( !Q.empty() ) {

  int x = Q.front().first;

  int y = Q.front().second;

  // idemo na sve cetiri strane.

  for( int i = 0; i < 4; ++i  ) {

    int X = x + dx[i], Y = y + dy[i];

    if( mapa[X][Y] == '#' ) continue;

    if( X < 0 || X >= Rows ) continue;

    if( Y < 0 || Y > Cols ) continue;

    if( bio[X][Y] != -1 ) continue;

    bio[X][Y] = bio[x][y] + 1; // onoliko koliko treba do pozicije s koje smo dosli do tu

    Q.push( make_pair( X, Y ) );

  }

}

Nakon sto smo nasli put, vracamo se od konacne tocke tako sto uvijek po matrici se moramo spustati gdje je vrijednost manja od 1.

Pametan nacin je rekurzivno.

Nesto ovako mozda :

void find_path( int x, int y ) {

  if( bio[x][y] == 0 ) return;

  for( int i = 0; i < 4; ++i ) {

    int X = x + dx[i];

    int Y = y + dy[i];

    if( bio[X][Y]+1 == bio[x][y] ) {

      mapa[X][Y] = 'O';

      find_path( X, Y );

      return;

    }

  }

}

Tako je, da fali popanje XD.

Ajmo reci da imamo ovakvu mapu.

....

x...

...p

ako krecemo od x "bio[][]" izgleda ovako:

1234

0123

1234

sada znamo koordinate od p. krecemo od p i moramo ici s 4->3->2->1->0.

kao sto vidimo postoji vise puteva(4), no nama je svejedno koji uzmemo.