Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Problem: Najveći pravougaonik u matrici

[es] :: Art of Programming :: Problem: Najveći pravougaonik u matrici

[ Pregleda: 3687 | Odgovora: 14 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

toroman
Srećko Toroman
www.wowd.com
Beograd / Banja Luka

Član broj: 52673
Poruke: 159
*.dialup.blic.net.

Sajt: toroman.wordpress.com


Profil

icon Problem: Najveći pravougaonik u matrici13.04.2006. u 21:42 - pre 219 meseci
Znači - data vam je neka matrica MxN sastavljena od jedinica i nula - problem je pronaći najveći pravougaonik jedinica.

Ovo je prošle godine u RS bilo na republičkom takmičenju (iirc) i nisam se mogao sjetiti (znati) koji je optimalan način za ovo.

Mislim da bi "sume" mogle pomoći (ne znam tačno ime, sorry, znam da ih još zovu tablice suma, ali ne sjećam se), ali nesiguran sam skroz, htio bih ovaj problem da razradim na času, pa bih vas zamolio da me usmjerite na pravo riješenje. Dakle ne tražim duga riješenja, već samo mi recite ime algoritma (odnosno slažete li se da bi se zadatak mogao uraditi preko suma).

Hvala.
Programeri su odgovorili na Hamletovo pitanje "Biti il ne biti?" :
0x2B | ~0x2B = 0xFF
(kao ono - ff - teško pitanje!)
 
Odgovor na temu

hatebreeder
Sinisa Bobic
Belgrade

Član broj: 48145
Poruke: 192
*.yubc.net.

Jabber: sinisabobic@gmail.com
ICQ: 339407553
Sajt: www.sinisabobic.com


Profil

icon Re: Problem: Najveći pravougaonik u matrici17.04.2006. u 17:35 - pre 219 meseci
Ako sam dobro shvatio nule su unutrasnjosti pravougaonika a jedinice okvir. Sigurno da od ove postoji bolja metoda al sta je tu je:

Za pocetak da napisem proceduru Oboji koju sigurno znas a trazi poziciju clanu matrice (x,y), "boju" izrazenu u integeru i matricu po kojoj cemo da zvrljamo:)

Code:

Procedure Oboji(x,y,boja:integer; var a:matrica);
 var
  temp:integer;
 begin
  temp:=a[x,y];
  a[x,y]:=boja;
  if temp=a[x+1,y] then Oboji(x+1,y,boja,a);
  if temp=a[x-1,y] then Oboji(x-1,y,boja,a);
  if temp=a[x,y+1] then Oboji(x,y+1,boja,a);
  if temp=a[x,y-1] then Oboji(x,y-1,boja,a);
 end;


E sad kad imamo tu proceduru protrcacemo kroz matricu i obojicemo je

Code:

B:=2; {'Krece od dva jel su 0 i 1 iskoristeni'}
for i:=1 to m do
 for j:=1 to n do if a[i,j]=0 then
  begin
   oboji(i,j,b,a);
   b:=b+1;
  end;


I na kraju prebebrojis koliko ima sa polja sa brojem 2, sa brojem 3 itd pa kojih ima najvise to je najveci pravougaonik a ako ti treba okvir onda sve to prebrojis pa kad lociras najvecu obojenu povrsinu jednostavno 2xduzina + 2xsirina + 4 (ovo cetri to su tacke na coskovima) nadam se da ce da ti radi posao ova ideja, ako ima nejasnoca slobodno pitaj
 
Odgovor na temu

D3adly

Član broj: 43272
Poruke: 35
*.cmu.carnet.hr.

ICQ: 281458481


Profil

icon Re: Problem: Najveći pravougaonik u matrici17.04.2006. u 20:20 - pre 219 meseci
to se lako rješava DP-om (dinamičkim programiranjem). Dakle, napraviš matricu u kojoj pamtiš koliko na nekom mjestu može biti maksimalni pravokutnik....


Flood fill-om nemožeš baš precizno odrediti jeli lik koji si obojao pravokutnik ili ne....
#include <D3adly.h>
 
Odgovor na temu

VeliborI

Član broj: 91798
Poruke: 1
213.149.112.*



Profil

icon Re: Problem: Najveći pravougaonik u matrici17.04.2006. u 22:04 - pre 219 meseci
Pomocu sledeceg koda dobijaju se sve podmatrice A[mi,ni] od matrice M[m,n] tako da vazi mi<=m, ni<=n:
Code:

for mi:=1 to m do
for ni:=1 to n do
for i:=1 to m-mi+1 do
for j:=1 to n-ni+1 do
begin
rezultat:=pravougaonik(i,j,i+mi-1,j+ni-1);
...
end;

gde funkcija pravougaonik(i,j,k,l) odredjuje dali podmatrica matrice M koja pocinje od i,j a zavrsava se sa k,l zadovoljava uslov zadatka.Rezultat se pamti i na kraju izbaci maksimalan.(M je globalna promenljiva)
Code:

function pravougaonik(i,j,k,l:integer):integer;
var n,m:integer;
begin
for n:= i to k do
for m:= j to l do
// sta se ispituje ?
... 
end; 

P.S. Zadatak nije jasno formulisan. Sta znaci najveci pravougaonik jedinica ?

Pozdrav ->

[Ovu poruku je menjao VeliborI dana 17.04.2006. u 23:14 GMT+1]

[Ovu poruku je menjao VeliborI dana 17.04.2006. u 23:28 GMT+1]
 
Odgovor na temu

hatebreeder
Sinisa Bobic
Belgrade

Član broj: 48145
Poruke: 192
*.yubc.net.

Jabber: sinisabobic@gmail.com
ICQ: 339407553
Sajt: www.sinisabobic.com


Profil

icon Re: Problem: Najveći pravougaonik u matrici17.04.2006. u 22:14 - pre 219 meseci
Citat:
D3adly: to se lako rješava DP-om (dinamičkim programiranjem). Dakle, napraviš matricu u kojoj pamtiš koliko na nekom mjestu može biti maksimalni pravokutnik....


Flood fill-om nemožeš baš precizno odrediti jeli lik koji si obojao pravokutnik ili ne....


Mozes nekom podfuncijom od dva reda proveriti veoma lako, Flood fill se prosto moze koristiti za sve ovakve poslove
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*



+1 Profil

icon Re: Problem: Najveći pravougaonik u matrici18.04.2006. u 14:47 - pre 219 meseci
Citat:
hatebreeder: Mozes nekom podfuncijom od dva reda proveriti veoma lako, Flood fill se prosto moze koristiti za sve ovakve poslove

Da samo sto je ta slozenost ogromna. Da ovo se trivijalno radi dinamickim programiranjem ko sto rece D3adly .
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

reiser

Član broj: 7895
Poruke: 2314



+102 Profil

icon Re: Problem: Najveći pravougaonik u matrici18.04.2006. u 15:06 - pre 219 meseci
Code:

const
  fieldWidth  = 10;
  fieldHeight = 10;
  field : Array[1..fieldWidth, 1..fieldHeight] of Integer = ((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, 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, 0, 0));

type
  TSolution = record
                StartX, EndX : Integer;
                StartY, EndY : Integer;
              end;


function ValidRect(const AStartX, AStartY, AEndX, AEndY : Integer) : Boolean;
var
  C1 : Integer;
begin
  result := FALSE;

  For C1 := AStartX to AEndX Do
    If field[AStartY, C1] = 0 Then
      Exit;
  For C1 := AStartX to AEndX Do
    If field[AEndY, C1] = 0 Then
      Exit;
  For C1 := AStartY to AEndY Do
    If field[C1, AStartX] = 0 Then
      Exit;
  For C1 := AStartY to AEndY Do
    If field[C1, AEndX] = 0 Then
      Exit;

  result := TRUE;
end;

function SolveField : TSolution;
var
  C1, C2 : Integer;
  C3, C4 : Integer;
begin
  result.StartX := 0;
  result.EndX := 0;
  result.StartY := 0;
  result.EndY := 0;

  If (fieldHeight <= 1) or
     (fieldWidth <= 1) Then
    Exit;

  For C1 := 1 to fieldHeight - 1 Do
    For C2 := 1 to fieldWidth - 1 Do
      If field[C1, C2] = 1 Then
        For C3 := fieldHeight downto C1 + 1 Do
          For C4 := fieldWidth downto C2 + 1 Do
            If (field[C3, C4] = 1) and
               ((result.EndX - result.StartX + 1) * (result.EndY - result.StartY + 1) < (C4 - C2 + 1) * (C3 - C1 + 1)) and
               (ValidRect(C2, C1, C4, C3)) Then
              Begin
                result.StartX := C2;
                result.EndX := C4;
                result.StartY := C1;
                result.EndY := C3;
              End;
end;


var
  solution : TSolution;

begin
  solution := SolveField;
end.


[Ovu poruku je menjao reiser dana 18.04.2006. u 16:06 GMT+1]
 
Odgovor na temu

hatebreeder
Sinisa Bobic
Belgrade

Član broj: 48145
Poruke: 192
*.yubc.net.

Jabber: sinisabobic@gmail.com
ICQ: 339407553
Sajt: www.sinisabobic.com


Profil

icon Re: Problem: Najveći pravougaonik u matrici18.04.2006. u 17:02 - pre 219 meseci
Ostajem pri flood filu samo dodacu kod za proveravanje da li je nesto pravougaonik (napisacu kako uopsteno proveriti da li je unutrasnjost pravougaonik, samim tim okvir mora biti pravougaonik)

Code:

function JestePravougaonik(x,y,boja:integer,a:matrica);
{'x jedna strana matrice, y druga strana matrice, boja je broj sa kojim je isfloodovana povrsina koju treba da proverimo
i a je matrica u kojoj sve to gledamo'}

var
 i,j:integer;
 x:array[1..5]of integer;
 temp:boolean;
begin
 for i:=1 to 5 do x[i]:=0;
 temp:=true;
 for i:=1 to x do
  for j:=1 to y do
   begin
    if a[i,j]=boja and a[i+1,j]=1 then x[1]:=x[i]+1;
    if a[i,j]=boja and a[i-1,j]=1 then x[2]:=x[i]+1;
    if a[i,j]=boja and a[i,j+1]=1 then x[3]:=x[i]+1;
    if a[i,j]=boja and a[i,j-1]=1 then x[4]:=x[i]+1;
    if a[i,j]=boja and a[i-1,j-1]=1 or a then x[5]:=x[i]+1;
    if a[i,j]=boja and a[i+1,j-1]=1 or a then x[5]:=x[i]+1;
    if a[i,j]=boja and a[i+1,j+1]=1 or a then x[5]:=x[i]+1;
    if a[i,j]=boja and a[i-1,j+1]=1 or a then x[5]:=x[i]+1;
   end;
 if x[1] <> x[2] then temp:=false;
 if x[3] <> x[4] then temp:=false;
 if x[5] <> 4 then temp:=false;
jestepravougaonik:=temp;
end;


ovo je samo ideja naravno kod moze u nesto manje linija jer direktno sam pisao pa nisam preterano mislio (mozda ima neka greska jer nisam istestirao al bitna je sustina):

-prvo smo obojili sva polja brojevima vecim od 2 i sad treba proveriti koji je najveci pravougaonik
-da bi nesto dolazilo uopste u pitanje da li je najveci pravougaonik moramo prvo pitati da li je uopste pravougaonik
-da bi dokazali da je pravougaonik mora da ima dva para ivica sa jednakim duzinama i mora da ima 4 temena (to u stvari radi funkcija)
-odrediti najveci pravougaonik po tome koliko polja zauzima

Nadam se da je ovo resenje koje smo trazili

[Ovu poruku je menjao hatebreeder dana 18.04.2006. u 18:03 GMT+1]
 
Odgovor na temu

toroman
Srećko Toroman
www.wowd.com
Beograd / Banja Luka

Član broj: 52673
Poruke: 159
*.dialup.blic.net.

Sajt: toroman.wordpress.com


Profil

icon Re: Problem: Najveći pravougaonik u matrici18.04.2006. u 21:43 - pre 219 meseci
Izvinjavam se što se dugo nisam javio.
Prvo da razjasnim neke nedoumice. Pod pravougaonikom jedinica podrazumijeva se *popunjen*
pravougaonik, znači sve jedinice. To vam dođe kao da se nalazite u nekoj "pećini" (dakle
nepravilnog oblika) i onda tražite gdje bi ste mogli staviti tepih što veće površine :)

Slažem se sa onima koji kažu da FloodFill nije za ovu upotrebu.

Još uvijek nisam vidio da mi je neko odgovorio na moj predlog da se problem riješi upotrebom
*kumulativnih* suma, pomoću kojih se traženi pravougaonik može naći algoritmom O(n^4).

Čini mi se da je reiser upotrebio Brute Force algoritam, međutim ako mogu da dodam, to riješenje
se može ubrzati ako umjesto funkcije "ValidRect" koristiš upravo pomenute sume. Dakle moje
riješenje ima istu složenost kao i reiser'ovo, ali sa manjim unutrašnjim "vremenom" (...)

Dalje mislim da se optimizacijom nekog od ponuđenih riješenja može dobiti prava stvar! Očigledno
je kod reiserovog primjera (i mog) da se neke stvari provjeravaju više nego što je potrebno,
evo dok ovo pišem, pada mi na pamet da bi se moj algoritam mogao znatno ubrzati, jednostavno
eliminacijom provjere slučajeva za koje sam već odredio da sigurno neće valjati, npr:

- ako se u pravougaoniku od (1,1) do (3,2) nalazi neka nula, onda nema svrhe provjeravati ijedan
drugi pravougaonik koji u sebi sadrži čitav pomenuti pravougaonik !!!

Ovo mi sve smrdi da nešto lagano, a opet mi nekako "bježi" (beži) :)

Pozdravljam poštovane sagovornike,
-- Toroman




[Ovu poruku je menjao toroman dana 18.04.2006. u 22:47 GMT+1]
Programeri su odgovorili na Hamletovo pitanje "Biti il ne biti?" :
0x2B | ~0x2B = 0xFF
(kao ono - ff - teško pitanje!)
 
Odgovor na temu

dimitar 16
Dimitar Misev
Makedonija

Član broj: 31509
Poruke: 134
*.ttnet.net.tr.

Jabber: dimitarmisev@gmail.com


Profil

icon Re: Problem: Najveći pravougaonik u matrici20.04.2006. u 11:35 - pre 219 meseci
Jel moze neko da napise to 'trivijalno' DP resenje od dva reda ?
 
Odgovor na temu

D3adly

Član broj: 43272
Poruke: 35
*.net.t-com.hr.

ICQ: 281458481


Profil

icon Re: Problem: Najveći pravougaonik u matrici20.04.2006. u 13:35 - pre 219 meseci
Oprostite, malo sam se zabunio, mislio sam da je riječ o kvadratu... Dinamičko rješenje za ovaj problem nikako nije 'trivijalno', kako bi bilo da je riječ o maxsimalnom kvadratu....

Malo pogleadaj na acm forum (problem 10043 je sličan) ...

#include <D3adly.h>
 
Odgovor na temu

dimitar 16
Dimitar Misev
Makedonija

Član broj: 31509
Poruke: 134
*.ttnet.net.tr.

Jabber: dimitarmisev@gmail.com


Profil

icon Re: Problem: Najveći pravougaonik u matrici20.04.2006. u 16:51 - pre 219 meseci
Isto i 108 - 'Maximum Sum'.
 
Odgovor na temu

toroman
Srećko Toroman
www.wowd.com
Beograd / Banja Luka

Član broj: 52673
Poruke: 159
*.dialup.blic.net.

Sajt: toroman.wordpress.com


Profil

icon Re: Problem: Najveći pravougaonik u matrici20.04.2006. u 22:23 - pre 219 meseci
Pardon, koji je to "acm" forum? Ako moze i link prema problemu,
bio bih veoma zahvalan :)

Rijesenje zaista nije trivijalno, ali opet, nekoliko ljudi ga je
rijesilo BF-om jer su ulazne matrice bile max velicine 10x10 :(
Programeri su odgovorili na Hamletovo pitanje "Biti il ne biti?" :
0x2B | ~0x2B = 0xFF
(kao ono - ff - teško pitanje!)
 
Odgovor na temu

D3adly

Član broj: 43272
Poruke: 35
*.net.t-com.hr.

ICQ: 281458481


Profil

icon Re: Problem: Najveći pravougaonik u matrici21.04.2006. u 08:28 - pre 219 meseci
ACM (početna stranica)

Problem 108 'Maximum sum'

Problem 10043

Forum


#include <D3adly.h>
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Re: Problem: Najveći pravougaonik u matrici21.04.2006. u 11:56 - pre 219 meseci
Ne znam kakve su sume u pitanju, ali ako je složenost od O(n^4) prihvatljiva, imam rešenje.
Code:
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;


int m,n;
vector< vector<int> > a;

void obradi()
{
    int best_p = 0;
    int x, y, best_w = 0, best_h = 0, best_x = 0, best_y = 0;
    
    for (x=0; x<m; x++)
    for (y=0; y<n; y++)
    {
        int x1, y1, loc_h=1;
        int max_y = n-1;
        
        if (a[x][y]==0)
        continue;
        
        for (x1=x; x1<m; x1++, loc_h++)
        {
        int p, loc_w;
        
        if (a[x1][y]==0)
            break;
        
        for (y1=y+1; y1<=max_y; y1++)
            if (a[x1][y1]==0)
            break;
            
        if (a[x1][y1]==0)
            max_y = --y1;
            
        loc_h = x1-x+1;
        loc_w = max_y-y+1;
        p = loc_w*loc_h;
        
        if (best_p<p)
        {
            best_p = p;
            best_w = loc_w;
            best_h = loc_h;
            best_x = x;
            best_y = y;
        }
        }
    }
    
    cout << "Najveci pravougaonik ima gornje levo teme na poziciji ("
         << best_x+1 << "," << best_y+1 << ") i povrsinu " << best_p
     << ".\nSirina mu je " << best_w
     << ", a visina " << best_h << "\n";
}

void ucitaj()
{
    ifstream ulaz("ulaz.txt");
    int x, y;
    
    ulaz >> m >> n;
    cout << m << "\n" << n << "\n";
    
    for (x=0; x<m; x++)
    {
    a.push_back(vector<int>());
    cout << "\n";
    
    for (y=0; y<n; y++)
    {
        int t;
        
        ulaz >> t;
        a[x].push_back(t);
        cout << t;
        
        if (y<n-1)
        cout << " ";
    }
    }
    
    cout << "\n";
}

int main()
{
    ucitaj();
    obradi();
    
    return 0;
}

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

[es] :: Art of Programming :: Problem: Najveći pravougaonik u matrici

[ Pregleda: 3687 | Odgovora: 14 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.