Algoritmas C++

Sveiki, terkime turiu matrica kurioje yra daug skirtingu spalvu kvadratu ir kai kurie vienodos spalvos lieciasi sonais. Apsiskaiciavau kieki kiek vienodos spalvos kubeliu kurie lieciasi sonais yra (kiekis). Dabar noreciau issaugoti kubeliu koordinates. Ar kazkas turite bent ideja kaip tai reiktu daryti? Pats galvoju kad reiktu daryti taip:

eiti per ta matrica ir fiksuoti pasirinktos spalvos pvz raudonos spalvos kubelius.

daryti if'a jei kubelis lieciasi su kitu kubeliu ir tas kitas kubelis liecasi dar su kitu mazinti kiekis-- (taip kol kiekis bus lygus 0)

jei if'as tenkinamas i kazkoki masyva ar dar kazkur saugoti tas koordinates.

Pereidamas matricą žymėkis kiekvieną spalvų grupę atskiru numeriu. Pavyzdžiui, turint tokią kubelių matricą:

A A B B B B A

A B B A A A A

B B A A A A A

A A A A A A B

A A A A A A B

A A A A A B B

C C C C C B C

Ir kol kas tusčią ID matricą:

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

Pradedam nuo langelio (1; 1) ir plečiamės į visas puses:

1 1 0 0 0 0 0

1 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

Tada kaip ir turėtume pradėti nuo (1; 2) langelio, bet jis jau užžymėtas (jo reikšmė vienetas), todėl praleidžiame ir šokame į (1, 3).

1 1 2 2 2 2 0

1 2 2 0 0 0 0

2 2 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

Vėlgi tęsiam ciklą, praleisdami langelius (1; 4:6) ir tęsdami su (1; 7).

1 1 2 2 2 2 3

1 2 2 3 3 3 3

2 2 3 3 3 3 3

3 3 3 3 3 3 0

3 3 3 3 3 3 0

3 3 3 3 3 0 0

0 0 0 0 0 0 0

Vėl praleisime dalį langelių, kol pasieksime (4; 7)

1 1 2 2 2 2 3

1 2 2 3 3 3 3

2 2 3 3 3 3 3

3 3 3 3 3 3 4

3 3 3 3 3 3 4

3 3 3 3 3 4 4

0 0 0 0 0 4 0

Tęsiam...

1 1 2 2 2 2 3

1 2 2 3 3 3 3

2 2 3 3 3 3 3

3 3 3 3 3 3 4

3 3 3 3 3 3 4

3 3 3 3 3 4 4

5 5 5 5 5 4 0

Dar ne pabaiga:

1 1 2 2 2 2 3

1 2 2 3 3 3 3

2 2 3 3 3 3 3

3 3 3 3 3 3 4

3 3 3 3 3 3 4

3 3 3 3 3 4 4

5 5 5 5 5 4 6

Kadangi visi langeliai jau gavo savo ID, tai šį etapą jau baigėm. Dabar, kad sužinotumėm, koks regionas didžiausias, suskaičiuojam langelius kiekvienam ID:

count[1] = 3;
count[2] = 8;
count[3] = 27;
count[4] = 5;
count[5] = 5;
count[6] = 1;

Nesunku pastebėti, kad didžiausiai grupei priklauso ID = 3. Belieka pereiti per visus ID matricos langelius ir jeigu tas langelis turi reikšmę „3“, jo koordinates išsisaugoti.

Dekui uz atsakyma, bet greiciausiai tavo nurodytas budas nebus tinkamas man, nes as Max'imum skaiciuoju visai kitoje funkcijoje.

void Kviesti(Kubas Kub, Kubai & Test, Kubai & Kubeliai, int p, int & kiekis, int & max, string & maxspalva, Maximumas Maxi[], int & ind, Koordinates Ko[], int & sk){
string Spal[3] = {"z", "r", "g"};
for(int sp=0; sp < 3; sp++){
	for(int i=1; i<Kub.ImtiX()-1; i++){
		for(int j = 1; j < Kub.ImtiY()-1; j++){
			Eiti(Test, Kubeliai, i, j, p, Spal[sp], kiekis, Ko, sk);
			Max(kiekis, max, maxspalva, Spal, sp, Maxi, ind, i, j, Ko, sk);
		}
	}
}
}

bool Eiti(Kubai & Test, Kubai & Kubeliai, int i, int j, int p, string spalva, int & kiekis, Koordinates Ko[], int & sk){
int tt = 0; // kaimyno numeris
bool yra = false;
if(Test.ImtiReiksme(i, j).ImtiSiena(p) == spalva){
	Test.DetiSP(i, j, p, "-");
	kiekis++;
	while(!yra && tt < 4 ){ // judejimas
		i = i + Test.ImtiEil(tt);
		j = j + Test.ImtiStu(tt++);
		if(Test.ImtiReiksme(i, j).ImtiSiena(p) == spalva){ // kelias
			Eiti(Test, Kubeliai, i, j, p, spalva, kiekis, Ko, sk);
		}
	}
}
return yra;
}

void Max(int & kiekis, int & max, string & s, string Spal[], int sp, Maximumas Maxi[], int & ind, int i, int j, Koordinates Ko[], int & sk){
if(kiekis!=0){
	Maxi[ind].Deti(kiekis, Spal[sp]);
	ind++;
}
if(max < kiekis){
	max = kiekis;
	kiekis = 0;
	s = Spal[sp];
}
else
	kiekis = 0;
}

Net jei ir maksimumą skaičiuoji pereidinėdamas pačią matricą, gali langeliams prisiskyrinėti ID. Tada tiesiog saugai, koks buvo maksimumas ir koks ID tam maksimumui. Lengelių atspausdinimas išlieka toks pat.

Net jei ir maksimumą skaičiuoji pereidinėdamas pačią matricą, gali langeliams prisiskyrinėti ID. Tada tiesiog saugai, koks buvo maksimumas ir koks ID tam maksimumui. Lengelių atspausdinimas išlieka toks pat.

Tada ID priskirciau paciam maksimumui o ne langeliams. Visas grazintas reiksmes is void kviesti as saugau cia

        if(kiekis!=0){
               Maxi[ind].Deti(kiekis, Spal[sp]);
               ind++;
       }

Jei kazkoki ID meginciau priskirinet as ji priskiriciau tam kiekiui, bet man reikia langelio koordinaciu. Nebent kazka ne taip supratau ka nori pasakyti.

Tada ID priskirciau paciam maksimumui o ne langeliams. Visas grazintas reiksmes is void kviesti as saugau cia

        if(kiekis!=0){
               Maxi[ind].Deti(kiekis, Spal[sp]);
               ind++;
       }

Jei kazkoki ID meginciau priskirinet as ji priskiriciau tam kiekiui, bet man reikia langelio koordinaciu. Nebent kazka ne taip supratau ka nori pasakyti.

ID turi priskirti ir langeliams, ir suskaičiuotam maksimumui. Tada, radus maksimalią grupę, belieką atspausdinti langelius, kurie turi maksimalios grupės ID.

ID turi priskirti ir langeliams, ir suskaičiuotam maksimumui. Tada, radus maksimalią grupę, belieką atspausdinti langelius, kurie turi maksimalios grupės ID.

As neturiu maksimalios langeliu grupes koordinaciu, todel taip padaryti negaliu, nes Funkcija Max as iskvieciu funkcijoje Kviesti. As gaunu visai kitokias koordinates. Be to praeidamas visa matrica as ja uzpildau

Test.DetiSP(i, j, p, "-");

(cia kad netikrintu dar karta tu langeliu) tai nelabai suvokiu kaip galima dar karta uzpildyti 1...9 ir t.t. Suprantu tavo ideja kad kiekviena grupe kazkokiu vis kitokiu simboliu nori uzpildyti ir tada skaiciuoti tu simboliu kieki, bet mano atveju (mano kode) to padaryti negalima. galiu tik max reiksmei prisikirti kazkoki tai simboli, bet langeliams ne.

jei if'as tenkinamas i kazkoki masyva ar dar kazkur saugoti tas koordinates.

Dekui uz atsakyma, bet greiciausiai tavo nurodytas budas nebus tinkamas man, nes as Max'imum skaiciuoju visai kitoje funkcijoje.

bool Eiti(Kubai & Test, Kubai & Kubeliai, int i, int j, int p, string spalva, int & kiekis, Koordinates Ko[], int & sk){
int tt = 0; // kaimyno numeris
bool yra = false;
if(Test.ImtiReiksme(i, j).ImtiSiena(p) == spalva){
	Test.DetiSP(i, j, p, "-");
	kiekis++;
	while(!yra && tt < 4 ){ // judejimas
		i = i + Test.ImtiEil(tt);
		j = j + Test.ImtiStu(tt++);
		if(Test.ImtiReiksme(i, j).ImtiSiena(p) == spalva){ // kelias
                               // Sitoj vietoj zymekis kazkur tai koordinates to kubelio, kuris tiko.
			Eiti(Test, Kubeliai, i, j, p, spalva, kiekis, Ko, sk);

		}
	}
}
return yra;
}

Taip neturi tikti, nes man reikia didziausio kibelio grupes koordinaciu (ji apsiskaiciuoju Max f-jije) todel si pasiulyta modifikacija netiktu.

Taip neturi tikti, nes man reikia didziausio kibelio grupes koordinaciu (ji apsiskaiciuoju Max f-jije) todel si pasiulyta modifikacija netiktu.

Nu kaip ne. Max funkcijoj sukeitinek ne tik kubeliu grupes dydi, bet kartu ir koordinates tos grupes. Gi pvz kai yra rikiavimas sakykime vardu ir pavardziu pagal varda, pvz: vardas1 < vardas2, todel sukeiciam vardas1 su vardas2 ir priedo sukeiti pavarde1 su pavarde2, taip ir cia daryk, suskaiciavai kubeliu grupes dydi, turi ju koordinates, padavei i max funkcija, jei naujai ateje duomenys didesni, sukeiti, kad max butu tie, kurie atejo i funkcija, lygiagreciai ir koordinates grupiu sukeiti. Kad dar aiskiau butu, funkcijoj "Eiti" susiradai grupes dydi bei ju koordinates, tada i max funkcija paduodi naujo_dydis + naujo_koordinates, funkcijoj tikrini, naujo_dydis > esamo_max_dydis, jei tenkina salyga, esamas_max_dydis = naujo_dydis, esamo_max_koordinates = naujo_koordinates.

Taip neturi tikti, nes man reikia didziausio kibelio grupes koordinaciu (ji apsiskaiciuoju Max f-jije) todel si pasiulyta modifikacija netiktu.

Toks jausmas, kad tu visiškai nesupranti, kaip ta tavo programa veikia... Mes tau sakom, kaip tau reiktų padaryti, o tu vis kartoji, kad netinka.

Yra trys variantai:

1. Kurį aš minėjau – pasižymėti kiekvieną langelį pagal grupės ID. Nejaugi atėjęs į langelį (x, y) ir pamatęs, kad jis tinka prie tavo dabartinės grupės, niekur negali pasižymėti, kad langelis priklauso tokiai ir tokiai grupei (langeliui (x, y) priskirti skaičiuką z)?
   
2. Kaip ir minėjo Hafnis, pereinant per visą grupę galima iškart saugoti tos grupės langelius. Nejaugi ir dabar negalima niekur išsaugoti, kad grupei, per kurią dabar einu, priklauso tokie ir tokie langeliai?
   
3. Galima dar prie maksimumo išsisaugoti vienintelį langelį, nuo kurio pereidinėjai grupę. Tada suradęs maksimumą ir žinodamas tos grupės vieną iš langelių, galėsi vėl pereiti visą tą grupę, tik šį kartą jau galėsi įsiminti/spausdinti tos grupės langelius.
   

Pirmas variantas įgyvendinamas labai nesudėtingai, antras variantas keblesnis dėl langelių įsiminimo pasirinktoje struktūroje, trečiam variantui reikalingi du šiek tiek besiskiriantys metodai grupės perėjimui.

Jeigu nei vienas iš galimų variantų netinka, tai reikia dartyti išvadas – gal tiesiog tavo programa netinkama.