dowiedzieć prostokątnych obszarów o określonych właściwościach w matrycy

Question

względu n * m matrycę z możliwych wartości o 1, 2 oraz pustego:

. . . . . 1 . . 
    . 1 . . . . . 1 
    . . . 2 . . . . 
    . . . . 2 . . . 
    1 . . . . . 1 . 
    . . . . . . . . 
    . . 1 . . 2 . . 
    2 . . . . . . 1 

ja wyszukać wszystkie bloki B (zawierających wszystkie wartości między (x0, Y0) i (x1, y1)), że

• zawierać co najmniej jeden '1'
• nie zawierają '2'
• nie są podzbiorem innego bloku z powyższych właściwości

przykład:

czerwony, zielony i niebieski powierzchnia wszystkich zawierać '1' nie '2', i nie jest częścią większego obszaru. Na tym zdjęciu są oczywiście więcej niż 3 takie bloki. Chcę znaleźć wszystkie te bloki.

Jaki byłby szybki sposób na znalezienie wszystkich tych obszarów?

Mam działające rozwiązanie brutalnej siły, iterując po wszystkich możliwych prostokątach, sprawdzając, czy spełniają one dwa pierwsze kryteria; następnie powtarzanie wszystkich znalezionych prostokątów, usuwanie wszystkich prostokątów zawartych w innym prostokącie; i mogę to przyspieszyć, najpierw usuwając kolejne identyczne wiersze i kolumny. Ale jestem dość pewny, że istnieje o wiele szybsza droga.

Answer 1

W końcu znalazłem rozwiązanie, które działa prawie w czasie liniowym (jest mały czynnik w zależności od liczby znalezionych obszarów). Myślę, że jest to najszybsze możliwe rozwiązanie.

Zainspirowany tej odpowiedzi: https://stackoverflow.com/a/7353193/145999 (zdjęcia zrobione również stamtąd)

Najpierw idę trought macierz przez kolumny, tworząc nową matrycę M1 pomiaru liczby kroków do ostatniego „1” i matrycę M2 pomiaru liczby kroków do ostatniego „2”

wyobrazić „1” lub „2” w którymś z szarymi blokami na powyższym zdjęciu

w końcu mam M1 i M2 patrząc tak:

nie przechodzą M1 i M2 w odwrotnej kolejności, w rzędzie:

I wykonać następujący algorytm:

foundAreas = new list() 

For each row y backwards: 
    potentialAreas = new List() 
    for each column x: 
     if M2[x,y]>M2[x-1,y]: 
      add to potentialAreas: 
       new Area(left=x,height=M2[x,y],hasOne=M1[x,y],hasTop=false) 
     if M2[x,y]<M2[x-1,y]: 
      for each area in potentialAreas: 
       if area.hasTop and area.hasOne<area.height: 
         add to foundAreas: 
          new Box(Area.left,y-area.height,x,y) 
      if M2[x,y]==0: delete all potentialAreas 
      else: 
       find the area in potentialAreas with height=M2[x,y] 
       or the one with the closest bigger height: set its height to M2[x,y] 
       delete all potentialAreas with a bigger height 

      for each area in potentialAreas: 
       if area.hasOne>M1[x,y]: area.hasOne=M1[x,y] 
       if M2[x,y+1]==0: area.hasTop=true 

teraz foundAreas zawiera wszystkie prostokąty o pożądanych właściwościach .

Answer 2

Możesz znaleźć się gdzieś pomiędzy rozpatrzeniem każdego prostokąta i odpowiednio sprytnym rozwiązaniem.

Na przykład, począwszy od każdego 1 można utworzyć prostokąt i stopniowo rozszerzać jego krawędzie na zewnątrz w 4 kierunkach. Zatrzymaj się, gdy uderzysz 2, zapisz ten prostokąt, jeśli (a) musiałeś zatrzymać się we wszystkich 4 kierunkach i (b) nie widziałeś tego prostokąta wcześniej.

Następnie z powrotem: musisz mieć możliwość wygenerowania czerwonego prostokąta i zielonego prostokąta, począwszy od 1 w pobliżu lewego górnego rogu.

Algorytm ten ma jednak kilka bardzo złych przypadków. Na myśl przychodzi wejście składające się ze wszystkich sprężyn 1. Musi więc być połączony z inną sprytnością lub pewnymi ograniczeniami na wejściu.

Answer 3

Rozważmy prostsze problemu jeden wymiar:

znaleźć wszystkie podciągi z .2.1.1...12....2..1.1..2.1..2 który zawiera co najmniej jedną 1 i nie 2 i nie są podciąg takiego łańcucha. Można to rozwiązać w liniowym czasie, wystarczy sprawdzić, czy między dwoma 2 jest 1.

Teraz można łatwo przystosować ten algorytm dla problemu dwa wymiary:

Dla 1≤i≤j≤n sumie wszystkie linie od i do j wykorzystujące następujące zarzuty: .+.=., .+1=1, .+2=2, 1+1=1, 1+2=2, 2+2=2 i zastosować jedną Algorytm wymiarowania do wynikowej linii.

Złożoność: O (n²m).