Jump to content
dranaxum

The Fill Algorithm

Recommended Posts

Posted

Algoritmul Fill

Problema

Fiind 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=4

matricea:

0 1 1 0

0 1 1 0

1 0 0 0

0 0 1 1

Se va afisa: 4, adica regiunea care cuprinde elementele: (1,2),(1,3),(2,2),(2,3)

Solutie

Se 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 0

0 2 2 0

3 0 0 0

0 0 4 4

Programul va afisa valoarea 4, care corespunde celei mai intinse regiuni de 1 (in matricea initiala).

DranaXum - http://hackpedia.info

Posted

foarte interesant..uite de ceva in genul avea nevoie lumea

acum 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 ";
}

ENUNT

Pe 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.

Posted
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 0

0 0 1 0

0 1 0 1

pentru

1,1 = 1

1,2 = 1

1,3 = 2

1,3 = 2

....

iese asta

1 1 2 2

1 2 4 4

1 2 5 5

1 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, y1

al doilea are x2, y2

pe post de coordonate

se face verificarea

daca

suma[x2,y2] - suma [x1, y1] = (x2 + 1) * (y2 + 1) - x1 * y1

aceasta 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,y

si (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 exemplu

1 0 1 0

0 1 1 0

0 0 1 0

0 1 0 1

ce 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 ?

@

Posted

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!

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



×
×
  • Create New...