dranaxum Posted February 3, 2008 Report Posted February 3, 2008 Algoritmul FillProblemaFiind data o matrice m x n, unde m,n apartin lui N si exista y elemente notate cu 1 si z elemente notate cu 0 iar y+z=m*n, aflati aria cea mai intinsa de elemente de 1.Exemplu:m=4, n=4matricea:0 1 1 00 1 1 01 0 0 00 0 1 1 Se va afisa: 4, adica regiunea care cuprinde elementele: (1,2),(1,3),(2,2),(2,3)SolutieSe foloseste algoritmul fill, care este o aplicatie a algoritmului backtracking in plan.#include<stdio.h>#include<conio.h>int a[100][100],n,m;int size;void fill(int i,int j,int k){ if(a[i][j]==1) { a[i][j]=k; // fiecarei element din regiune ii corespunde numarul zonei size++; /*verificam daca elementele alaturate pot apartine aceiasi regiuni si daca nu au fost inca marcate*/ if(a[i-1][j]==1) fill(i-1,j,k); if(a[i+1][j]==1) fill(i+1,j,k); if(a[i][j-1]==1) fill(i,j-1,k); if(a[i][j+1]==1) fill(i,j+1,k); }}int main(){ int i,j; FILE *fin=freopen("fill.in","r",stdin); FILE *fout=freopen("fill.out","w",stdout); scanf("%d%d",&m,&n); for(i=1;i<=m;i++) for(j=1;j<=n;j++) scanf("%d",&a[i][j]); int max=0; int k=1; for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(a[i][j]==1){ k++; //fiecarei regiuni ii va corespunde un numar de ordine size=0;//numarul de elemente dintr-o regiune este initial 0 fill(i,j,k); if(max<size) max=size;//calculam maximul ariilor } printf("%d",max); fclose(fin); fclose(fout); return 0;}Dupa incheierea programului matricea data ca exemplu va arata astfel:0 2 2 00 2 2 03 0 0 00 0 4 4Programul va afisa valoarea 4, care corespunde celei mai intinse regiuni de 1 (in matricea initiala).DranaXum - http://hackpedia.info Quote
&#208;&#210;& Posted February 3, 2008 Report Posted February 3, 2008 foarte interesant..uite de ceva in genul avea nevoie lumeaacum sa prezint si eu ce am lucrat la backtracking in plan.#include <iostream>#include <stdlib.h>using namespace std;int tabla[100][100],n,xi,yi,sol=0;;void citire() { int i,j; cout << "n"; cin >> n; for (i=1; i<=n; i++) for (j=1; j<=n; j++) { cin >> tabla[i][j]; if (tabla[i][j] == 2) { xi = i; yi = j; } } }void back(int x,int y) { if (tabla[x][y] == 3 ) { cout << "Tura a ajuns la pozitia finala care este " << tabla[x][y]; return; } else { tabla[x][y] = 1; if (x + 1 <=n && (tabla[x+1][y]!=1) && (tabla[x+1][y]!=2)) back(x+1,y); if (x - 1 > 0 && (tabla[x-1][y]!=1) && (tabla[x-1][y]!=2)) back(x-1,y); if (y - 1 > 0 && (tabla[x][y-1]!=1)&& (tabla[x][y-1]!=2)) back(x,y-1); if (y+1 <=n && (tabla[x][y+1]!=1) && (tabla[x][y-1]!=2)) back(x,y+1); tabla[x][y] = 0;}}int main() { citire(); back(xi,yi); cout << "nu s a gasit solutie ";} ENUNTPe o tabla de sah de dimensiune n*n weste plasata o tura pe pozitia (x0,y0),Scrieti un program care sa verifice daca poate ajunge la (x1,y1),deplasandu se numai pe pozitii libere.Rezolvare:O sa avem o mica legenda:0 - pozitie libera.1 - pozitie ocupata.2 - inceput.3 - sfarsit.In rest se ia cele 4 puncte cardinale in ordine si se verifica daca se poate ajunge pe ele.altfel ne intoarcfem din apel..le dam 1 la cele intoarse ca sa prevenim o ciclare a pozitiilor. Quote
moubik Posted February 3, 2008 Report Posted February 3, 2008 Algoritmul Fill...o problema asemanatoare dar putin mai complexa am avut la un concurs national.rezolvarea cu mai putine iteratii si mai putina memorie ocupata arata asa:se precalculeaza la inceput ceva. e greu de explicat in scris. sa-mi spui daca se intelege.pentru fiecare punct de pe matrice se calculeaza suma elementelor de la 1,1 la i,j.Exemplu pentru matricea aceasta:1 0 1 0 0 1 1 00 0 1 00 1 0 1pentru 1,1 = 11,2 = 11,3 = 21,3 = 2....iese asta1 1 2 21 2 4 41 2 5 51 3 5 6(apropo, rezolvarea ta e gresita, iti explic la sfarsit)din aceasta matrice putem sa aflam care este cel mai mare dreptunghi complet.se face n^4 pe ea, deci se verifica fiecare punct cu fiecare punct.sa spunem ca primul punct de pe matrice are x1, y1al doilea are x2, y2pe post de coordonatese face verificarea daca suma[x2,y2] - suma [x1, y1] = (x2 + 1) * (y2 + 1) - x1 * y1aceasta verificare practic verifica daca "aria" dintre cele 2 puncte este plina de 1.observi ecuatia si vezi ca in suma[x,y] ai de fapt aria de la 1,1 pana la x,ysi (x2 + 1) * (y2 + 1) - x1 * y1 este aria intre cele 2 puncte.deci tu ai deja (aproape) precalculata aria, verifici daca este egala.ai complexitate n^4 asa dar numarul de iteratii scade foarte mult.rezolvarea ta este gresita pentru ca pe o matrice ca in exemplu1 0 1 0 0 1 1 00 0 1 00 1 0 1ce este cu rosu este identificat de algoritmul tau ca fiind dreptunghi.tu nu faci verificare daca este dreptunghi sau nu, ci doar daca poti sa mergi pe cele 4 directii.am dreptate ?edit: sau nu am inteles eu bine cerinta ?@ Quote
&#208;&#210;& Posted February 3, 2008 Report Posted February 3, 2008 trebuia sa aiba un exit(0) acolo. Quote
&#208;&#210;& Posted February 3, 2008 Report Posted February 3, 2008 pai poate e pt orice secventa de 1 care e adiacenta a lui dranaxum,adica orice figura nu doar dreptunghi. Quote
dranaxum Posted February 3, 2008 Author Report Posted February 3, 2008 moubik ce zici tu este o hmmm problema POSIBILA la fill dar NU este fill.Fill-ul doar calculeaza aria regiunilor care pot fi sau nu dreptunghiuri.Da, in a 9a am dat la nationala de acest algoritm, se facea fill apoi trebuia sa verifici daca se formeaza un dreptunghi.Insist ca algoritmul NU este gresit! Quote
moubik Posted February 3, 2008 Report Posted February 3, 2008 ok, nu am inteles eu bine enuntul problemei atunci, scuze edit: incearca totusi sa intelegi algoritmul pe care l-am expus. poate te ajuta o data Quote
phreak Posted February 3, 2008 Report Posted February 3, 2008 nici eu nu am inteles enuntul vezi poate reformulezi dranaxum : "unde m,n N" wtf? Quote
dranaxum Posted February 3, 2008 Author Report Posted February 3, 2008 Da mam uitat pe el, lam inteles e calumea , "smen" edit: am modificat acolo din cauza ca eu il scrisesem prima data in word si am folosit equation editor Quote
&#208;&#210;& Posted February 3, 2008 Report Posted February 3, 2008 poate vrea sa zica apartine multimi nr naturale. Quote
tiesto41 Posted February 3, 2008 Report Posted February 3, 2008 apoi voi fratzilor mergeti prin mate ca si cutzitu prin unt.. Quote
dranaxum Posted February 3, 2008 Author Report Posted February 3, 2008 no shit man!! --> vezi mai sus de ce a aparut asa Quote
&#208;&#210;& Posted February 3, 2008 Report Posted February 3, 2008 puteai sa pui semnul de la euro..dar in fine nu are importanta.Tiestoi asta e informatica nu vezi bine? Quote