Problem: Najveći pravougaonik u matrici

[ toroman @ 13.04.2006. 21:42 ] @

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.

[ hatebreeder @ 17.04.2006. 17:35 ] @

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

[ D3adly @ 17.04.2006. 20:20 ] @

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

[ VeliborI @ 17.04.2006. 22:04 ] @

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]}

[ hatebreeder @ 17.04.2006. 22:14 ] @

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

[ cassey @ 18.04.2006. 14:47 ] @

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 .

[ reiser @ 18.04.2006. 15:06 ] @

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]}

[ hatebreeder @ 18.04.2006. 17:02 ] @

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]}

[ toroman @ 18.04.2006. 21:43 ] @

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]}

[ dimitar 16 @ 20.04.2006. 11:35 ] @

Jel moze neko da napise to 'trivijalno' DP resenje od dva reda ?

[ D3adly @ 20.04.2006. 13:35 ] @

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

[ dimitar 16 @ 20.04.2006. 16:51 ] @

Isto i 108 - 'Maximum Sum'.

[ toroman @ 20.04.2006. 22:23 ] @

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 :(

[ D3adly @ 21.04.2006. 08:28 ] @

ACM (početna stranica)

Problem 108 'Maximum sum'

Problem 10043

Forum

[ Nedeljko @ 21.04.2006. 11:56 ] @

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