BFS(breath first search) KOD

This message was edited 1 time. Last update was at 28/02/2013 14:13:24

Aj nekoj neka mi brz kod za bfs!! mi treba za da ja resam ovci, no mi paga na vreme zaradi bfsto! fala odnapred

This message was edited 1 time. Last update was at 17/06/2011 17:27:27

Sakas kod od ovci zadacata?
Minuva na bfs. (0,109 сек.) najgolemoto resenie

OP Magic Potato wrote:Aj nekoj neka mi brz kod za bfs!! mi treba za da ja resam ovci, no mi paga na vreme zaradi bfsto! fala odnapred

еве ти бфс псеудо (wiki)

bedzo wrote:Sakas kod od ovci zadacata?
Minuva na bfs. (0,109 сек.) najgolemoto resenie

Kako sto razbrav, go saka samo delot so bfs-to.

Ти имаш искуцано споро BFS? Може да го пратиш да го видиме?

support за кико , и ја сакам да го видам кодот

This message was edited 2 times. Last update was at 18/06/2011 13:24:32

ova e mojot kod za ovci:

#include <iostream>

using namespace std;

char ma[250][250];// 'ma' mi e pocetnata matrica
int krajo=0, krajv=0,r, c;// krajo mi e brojac za ovcite, krajv za volcite; 'r' mi se redicite, 'c' mi se kolonite
void bfs(){
    int o=0,v=0;
    int br[r][c];// br mi e matrica kade gi obelezuvam polinjata sto gi pominalo bfsto
    bool t = true;
    for(int i=0;i<r;i++){// ovde ja odreduvam pocetnata tocka od kade da pocne so prebaruvanje
        for(int j=0;j<c;j++){
            br[i][j]=0;
            if(t==true&&ma[i][j]!='#'){
                br[i][j]=1;
                t = false;
                if(ma[i][j]=='o')o++;
                else if(ma[i][j]=='v')v++;
                ma[i][j]='#';
            }
        }
    }
    //ova mi e pocetok na bfsto ---------->>>>
    int k= 1,temp = 1;
    while(k>0){
        k=0;
        for(int i=0;i<r;i++){// ja pominuva celata matrica se dodeka ne najde pome obelezano so 'temp' i od toa pole se siri za edno gore, dolu, levo i desno dokolku e mozno
            for(int j = 0;j<c;j++){// ovoj proces se povtoruva se dodeka e mozno da se siri(brojacot 'k' mi oznacuva dali sum obelezal drugi polinja)
                if(br[i][j]==temp){
                    if(i+1<r&&ma[i+1][j]!='#'){
                        br[i+1][j]=temp+1;
                        k++;
                        if(ma[i+1][j]=='o')o++;
                        else if(ma[i+1][j]=='v')v++;
                        ma[i+1][j]='#';
                    }
                    if(i-1>=0&&ma[i-1][j]!='#'){
                        br[i-1][j]=temp+1;
                        k++;
                        if(ma[i-1][j]=='o')o++;
                        else if(ma[i-1][j]=='v')v++;
                        ma[i-1][j]='#';
                    }
                    if(j+1<c&&ma[i][j+1]!='#'){
                        br[i][j+1]=temp+1;
                        k++;
                        if(ma[i][j+1]=='o')o++;
                        else if(ma[i][j+1]=='v')v++;
                        ma[i][j+1]='#';
                    }
                    if(j-1<c&&ma[i][j-1]!='#'){
                        br[i][j-1]=temp+1;
                        k++;
                        if(ma[i][j-1]=='o')o++;
                        else if(ma[i][j-1]=='v')v++;
                        ma[i][j-1]='#';
                    }
                }
            }
        }
        temp++;
    }
//ovca mi e kraj na bfsto ---------------------<<<<

if(o>v)krajo+=o;
    else krajv+=v;
}

int main(){
    cin >> r >> c;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin >> ma[i][j];
        }
    }
    bool t = true;
    while (t ==true){
        int i=0;
        t = false;
        while (i<r&&t==false){
            int j = 0;
            while (j<c&&t==false){
                if(ma[i][j]!='#')t = true;
                j++;
            }
            i++;
        }
        if(t==true)bfs();
    }
    cout << krajo << " "<<krajv;
    return 0;
}

^
Разгледај го ова http://www.cplusplus.com/reference/stl/queue/

Ти треба уште кодот со бфс?

ne be, uzivaj!!! xD

епа нека ја тргнат темата од важна :Р

Најбрз начин за Овци е класичен flood fill . Многу поедноставен од BFS, во многу помалку реда.

tone wrote:Најбрз начин за Овци е класичен flood fill . Многу поедноставен од BFS, во многу помалку реда.

А со bfs не се прави flood fill нели?

)

1. Види ја датата на темата.

2. Класичен flood fill? Ова сакам да го видам, исто како спорото BFS...

This message was edited 2 times. Last update was at 26/09/2012 19:52:27

Не е спор, најдолгото решение е 0.015 секунди. 50 реда, во Pascal. Во право си kenobi, off topic заминав, се извинувам. Еве го кодот:

program ovci;
var
   zivO,zivV,lokO,lokV,redici,koloni,i,j:integer;
   a:array[0..250,0..250]of char;
procedure popolni(redica,kolona:integer);
begin
   if a[redica,kolona]<>'#' then begin
      if a[redica,kolona]='.' then begin
         a[redica,kolona]:='#';
         if a[redica,kolona+1]<>'#' then popolni(redica,kolona+1);
         if a[redica,kolona-1]<>'#' then popolni(redica,kolona-1);
         if a[redica+1,kolona]<>'#' then popolni(redica+1,kolona);
         if a[redica-1,kolona]<>'#' then popolni(redica-1,kolona);
      end;
      if a[redica,kolona]='v' then begin
         lokV:=lokV+1;
         a[redica,kolona]:='#';
         if a[redica,kolona+1]<>'#' then popolni(redica,kolona+1);
         if a[redica,kolona-1]<>'#' then popolni(redica,kolona-1);
         if a[redica+1,kolona]<>'#' then popolni(redica+1,kolona);
         if a[redica-1,kolona]<>'#' then popolni(redica-1,kolona);
      end;
      if a[redica,kolona]='o' then begin
         lokO:=lokO+1;
         a[redica,kolona]:='#';
         if a[redica,kolona+1]<>'#' then popolni(redica,kolona+1);
         if a[redica,kolona-1]<>'#' then popolni(redica,kolona-1);
         if a[redica+1,kolona]<>'#' then popolni(redica+1,kolona);
         if a[redica-1,kolona]<>'#' then popolni(redica-1,kolona);
      end;
   end;
end;
begin
   readln(redici,koloni);
   for i:=1 to redici do begin
      for j:=1 to koloni do read(a[i,j]);
      readln;
   end;
   zivO:=0; zivV:=0;
   for i:=1 to redici do
      for j:=1 to koloni do
         if a[i,j]<>'#' then begin
            lokO:=0;
            lokV:=0;
            popolni(i,j);
            if lokO>lokv then zivO:=zivO+lokO else zivV:=zivV+lokV;
         end;
   writeln(zivO,' ',zivV);
   readln();
end.