The Fill Algorithm

[dranaxum]

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

[ÐÒ&]

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.

[moubik]

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 ?

@

[ÐÒ&]

trebuia sa aiba un exit(0) acolo.

[ÐÒ&]

pai poate e pt orice secventa de 1 care e adiacenta a lui dranaxum,adica orice figura nu doar dreptunghi.

[dranaxum]

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!

[moubik]

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

[phreak]

nici eu nu am inteles enuntul vezi poate reformulezi dranaxum :

"unde m,n N" wtf?

[dranaxum]

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

[ÐÒ&]

poate vrea sa zica apartine multimi nr naturale.

[tiesto41]

apoi voi fratzilor mergeti prin mate ca si cutzitu prin unt..

[dranaxum]

no shit man!! --> vezi mai sus de ce a aparut asa

[ÐÒ&]

puteai sa pui semnul de la euro..dar in fine nu are importanta.

Tiestoi asta e informatica nu vezi bine?