Bangos algoritmas

Sveiki, turiu klausima ar kazka zinot apie bangos algoritma? Internete visiskai nieko nera.... Turiu kazkaip surasti didziausia vienos spalvos kubeliu skaiciu kurie lieciasi bent vienu tasku.... Destytojo klausiau ir jis tik numete kad kazkur yra bangos algoritmas, nieko taip ir negalejas detaliau paasikinti, internete tik apie sinusu bangas pasakoja kas man visiskai netinka... bandziau pats galvoti bet niekaip neusimastau algoritmo. Zodziu gal kas galit paaiskinti ta bangos algoritma ar kazkoki konkretesni pavyzdy duoti? Dekui

Pats mastau sitaip

Test(ind, ind2){
for(int i=1 (arba indx); i<=n; i++){
for(int j=1 (arba indj); j<=m; j++){
int inndx;
int indj;
  if(KubelioSpalva(i, j) == KubelioSpalva(i+1, j) ||
     KubelioSpalva(i, j) == KubelioSpalva(i-1, j) ||
     KubelioSpalva(i, j) == KubelioSpalva(i, j+1) ||
     KubelioSpalva(i, j) == KubelioSpalva(i, j-1)){
       kiek++;
       indx = i;
       indj = j;
  }
else
Test(indx, indj);
}
}
}

http://100byte.ru/100btwrks/wv/wv.html

Dekui, bet nors rusiskai nelabai ka ir suprantu man atrodo kad cia greiciausio kelio algoritmas, o man reikia vienoje plokstumoje esanciu ir besiliecianciu kubeliu ilgiu surasti. Sis algoritmas nemanau kad yra tinkamas tam, bet aciu reikes kazkaip destytojo issiklausineti jei pats nieko padoraus nesugalvosiu...

Ar sita dalyka imanoma apskritai be bangos algoritmo padaryti?

jauciu darai labora KTU :) visi su situ dalyku kliuva. Ir tuose pavyzdziuose absoliuciai nera tinkamu pavyzdiu, o paciu funkciju ir algoritmu nelabai ten jau ir rodo. Temos naujos kurti nesinori ir klausimas mano butu tas pats kaip apskaiciuoti daugiausiai vienos spalvos kubeliu kieki (jie privalo visi liestis) je tarp ju yra kitokios spalvos kubelis taip iseina kad tos dvi dalys (pavyzdyje pavaizduotos raudonai) yra atskiros. P.S nezinau bet as su profesoriumi tada niekaip nesutikciau, nes netikiu kad cia reikia NE BANGOS ALGORITMO :/ manau kad cia tinkamesne paieska gilyn, su kuri taip pat nieko doro nesigauna...

http://en.wikipedia....th-first_search

ps. kelintam kurse tokias užduotis duoda?

Patys gi galit išmastyt tą algortimą, nėra čia nieko sudėtingo jau bent iš pirmo žvilgsnio, netinget galva tik pasukti :D

http://en.wikipedia....th-first_search

 

ps. kelintam kurse tokias užduotis duoda?

1-ame kurse :)

Aš įsivaizduoju tokį algoritmą:

• eini per kubelius standartine seka, iš kairės į dešinę, iš viršaus žemyn
• kiekvienai naujai aptiktai spalvai suformuoji lauko dydžio matricą, jei tokia matrica jau yra patikrini ar laukas toje pozicijoje jau joje apibrėžtas, jei ne, tada sukuri atskirą matricą traktuodamas tai kaip naują lauką, jei yra - praleidi
• sukūręs kiekvieną naują matricą perduodi esamas koordinates ir spalvą rekursinei funkcijai kuri juda per kubelius medžio algoritmu tikrindama 3 artimiausius dar neaplankytus kaimynus ir jei spalvos sutampa talpina juos matricoję
• pabaigoje sulygini gautų matricų dydžius ir štai atsakymas

http://en.m.wikipedia.org/wiki/Connected-component_labelin,

Pasiskaityk čia, panašiai turėtum daryti kaip two-pass algoritme (tik atmesk nereikalingus veiksmus, pavyzdžiui, union set sudarymą). Gausi matricą, kurioje kiekvienas langelis saugos regiono, kuriam šis langelis priklauso, numerį. Tada beliks suskaičiuoti, kokio numerio langelių daugiausia ir grąžinti jų skaičių.

Priklausomai nuo užduoties gali reikti vaiksčioti ne tik į langelių iš dešinės, kairės, viršaus ir apačios, bet ir įstrižai.

Mendinski, stai ka pasirasiau

bool Eiti(Kubai & kok, Kubai & Kubeliai, int i, int j, string spalva, int p, int & kiekis){
int tt = 0; // kaimyno numeris
bool yra = false;
int max = 0;
	if(kok.ImtiReiksme(i,j).ImtiSiena(5) == spalva){
	kok.DetiSP(i, j, p, "-");
	kiekis++;
		while(!yra && tt < 4){ // !yra = true
			 i = i + kok.ImtiEil(tt);
			 j = j + kok.ImtiStu(tt++);
			if(kok.ImtiReiksme(i, j).ImtiSiena(p) == spalva){
				Eiti(kok, Kubeliai, i, j, spalva, p, kiekis);
			}
		}
	}
return yra;
}

Maine kvieciu

for(int i = 1; i<Kub.ImtiX()-1; i++){
	for(int j = 1; j < Kub.ImtiY()-1; j++){
		for(int sp=0; sp<3; sp++){
			Eiti(test, Kubeliai, i, j, Spal[sp], virsune, kiekis);
		}
		if(max < kiekis){
			max = kiekis;
			kiekis = 0;
		}
		else
		{
			kiekis = 0;
		}
	}
}

Tik yra vienas klausimas as dabar gaunu didziausia kubeliu kieki, o man ji dar ir reikia nuspalvinti "x", bet siuo algoritmu neisena pozicijos kubelio issaugoti :/ nes max'imumas apskaiciuojamas main'e ar imanoma kazkaip issaigoti kubo pozicija ir ji spalvinti? Dekui uz atsakyma.

Dekui, kazka panausaus praktiniuose pavyzdziuose buvau rades, bet nemanau kad su juo tau kazkaip iseis nuspalvinti tam tikrus langelius. Tu langeliu pozicijos neissisaugai (ko cia padaryti man atrodo nera imanoma, nes max tu apsiskaiciuoji main'e), todel turi kazkokia stambi modifikacija buti, bet tikrai nepajegiu isivaizduoti kokia net.

Sprendimo idėją, kaip ir kalbėta anksčiau - keliauji per visą simbolių lentelę, ir jei randi nenuspalvintą elementą, tai spalvindamas tą pačią elementų grupę lentelėje apskaičiuoj jo dydį. Ir taip keliauji iki paskutinio lentelės elemento. Taškas žymi, jog lentelės elementas nuspalvintas. Gal kam bus įdomu. :)

program Noname0;
const dfilename = 'ba.txt';
     MAX1 = 100;
     MAX2 = 100;
type TMas = array [0..MAX1+1, 0..MAX2+1] of char;

var
 m: Tmas;

procedure Skaityti (var m: Tmas; var ik, jk: integer);
var byla: text;
   i, j: integer;
begin
 Assign (byla, dfilename);
 Reset (byla);
 Readln (byla, ik, jk);
 for i := 1 to ik do
   begin
     for j := 1 to jk do
       Read (byla, m[i, j]);
     Readln (byla);
   end;
 Close (byla);
end;

procedure Paruosti (var m: Tmas);
var byla: text;
   i, j: integer;
begin
 for i := 0 to MAX1 do
  for j := 0 to MAX2 do
    m [i, j] := '.';
end;

procedure ieskoti (i, j: integer; var mx: integer);
var c : char;
begin
 if m [i, j] <> '.' then
  begin
    c := m [i, j];
    m [i, j] := '.';
    mx := mx + 1;
    if m [i-1, j] = c then ieskoti (i-1, j, mx);
    if m [i+1, j] = c then ieskoti (i+1, j, mx);
    if m [i, j-1] = c then ieskoti (i, j-1, mx);
    if m [i, j+1] = c then ieskoti (i, j+1, mx);
  end
end;

var
 maxs, ik, jk, i, j, mx : integer;
begin
 Paruosti (m); maxs := 0;
 Skaityti (m, ik, jk);
 for i := 1 to ik do
   for j := 1 to jk do
     if m [i, j] <> '.' then
      begin
        mx := 0;
        ieskoti (i, j, mx);
        if mx > maxs then maxs := mx;
     end;
 Writeln (maxs);
 Readln;
end.