Backtracing im Array

[ThoPie]

Hallo,

Ich habe ein Array der Dimension 12 x 12.
Die Elemente des Array sind entweder 0 oder 1. Nun möchte ich prüfen, ob eine "Verbindung von 1-Elementen" zwischen Spalte 1 und Spalte 12 (quasi dem linken und rechten Rand) besteht, wobei keine diagonalen Verbindungen zugelassen sind.
Ich hoffe ich habe mich einigermaßen verständlich ausgedrückt und hoffe auf eure Hilfe.

Thx

[Kaeru Gaman]

Code: Alles auswählen

For Spalte = 0 to 11
   If Array(Spalte, 0) And Array(Spalte, 11)
      ; Verbindung besteht
   EndIf
Next

so in der richtung?

[ThoPie]

Naja, die Verbindung muss nicht "geradlinig" sein - es soll also ermittelt werden, ob irgendein beliebiger Weg vom der Spalte 1 zur Spalte 12 besteht.

[Kaeru Gaman]

ach SO

ich dachte, du meinst eine verbindung um die falte drumrum, also, weiterleitend sozusagen.

du meinst also, ob ein weg über das array besteht, also, eine verbindung.

jetzt versteh ich. da bist du mit dem stichwort "backtracking" bzw. "backtracing" schon ganz richtig.

boah, wie erklärt man das jetzt mal eben auf die schnelle.

[ullmann]

Ist folgendes Bitfeld ein gültiger Weg?

• 000000000000
  000011111111
  000010000000
  000011100000
  111000100000
  001000100000
  001111100000
  000000000000
  ...

Rainer

[ullmann]

Folgender Algorithmus müsste funktionieren:

Code: Alles auswählen

Du gehst in Spalte 0 beginnend bei Zeile 0 solange nach unten, bis du eine 1 findest oder Zeile 12 erreichst. Hast du Zeile 12 erreicht, gibt es keinen Weg.

Hast du eine 1 gefunden, startest Du folgenden Suchlauf:

  Das Feld mit der 1 wird in eine Liste "Fertig" eingetragen.
  Ist von dem soeben eingetragen Feld die Spalte=12 so existiert ein Weg. Ende.
  Ansonsten untersuchst Du die 4 Nachbarfelder Ost, Süd, West und Nord:
    Wenn das Nachbarfeld im Array liegt - und-
    wenn das Nachbarfeld eine 1 ist - und -
    wenn das Nachbarfeld nicht in der Liste "Fertig" enthalten ist,
      dann trage das Nachbarfeld in eine Liste "Offen" ein
  tu das für alle 4 Nachbarfelder.
  Wenn die Liste "Offen" leer ist, so war es eine Sackgasse, 
    (wenn Du Suchzeit sparen möchtest lösche die Liste Fertig, nicht zwingend erforderlich)
    suche in der Hauptschleife in Spalte 0 abwärts die nächste 1.
  Wenn die Liste "Offen" nicht leer ist, so entnimm ein Feld (lösche es in der Liste "Offen")
    und starte den Suchlauf erneut, d.h. trage das Feld in die Liste "Fertig" ein usw.

Rainer

[#NULL]

vielleicht vorher prüfen ob es eine spalte gibt, welche nur nullen enthält. dann gäbe es einen solchen weg schonmal nich.

[ThoPie]

Danke erstmal - werde den Algo von ullmann mal versuchen umzusetzen und auch den Tipp von #Null mit einbauen.

[#NULL]

diese programm findet nicht den kürzesten weg!
es findet nur raus, ob es einen weg gibt.
is das erste mal, dass ich wegfindung programmiert hab. is also nich besonders performant, und es gibt auf jeden fall cleveres (oder clevereres?).

Code: Alles auswählen

OpenConsole()
#wahrscheinlichkeit=2 ; look at line 15-17
Global xMax=11
Global yMax=11
Global Dim a(xMax,yMax) ; source/input array
Global Dim closed(xMax,yMax) ; list of analized points
Global Dim open(xMax,yMax) ; list of linked but not analized points

For k=0 To yMax
  For i=0 To xMax
    If Random(#wahrscheinlichkeit)
      a(i,k)=1
    EndIf
  Next
Next

Declare.b openPointsLeft() ;returns boolean
Declare checkAdjacentPoints(x,y)
Declare.b withinArrayBounds(x,y) ; returns boolean
Declare showMap()


;###########################################   MAIN   #######################
For z=0 To yMax
  If a(0,z)
    ;Dim closed(0,0) : Dim closed(xMax,yMax)
    ;Dim open(0,0) : Dim open(xMax,yMax)
    open(0,z)=1
    While openPointsLeft()
      For k=0 To yMax
        For i=0 To xMax
          If open(i,k)
            If i=xMax ;this is a valid way
              closed(i,k)=1
              showMap()
              Print("!!! HEUREKA !!!")
              Input()
              End
            Else
              checkAdjacentPoints(i,k)
            EndIf
          EndIf
        Next
      Next
    Wend
  EndIf
Next
showMap()
Print("<DAMN>")
Input()
End
;############################################   MAIN END   #####################


Procedure.b openPointsLeft()
  For k=0 To yMax
    For i=0 To xMax
      If open(i,k)
        ProcedureReturn 1
      EndIf
    Next
  Next
  ProcedureReturn 0
EndProcedure

Procedure checkAdjacentPoints(x,y)
  If withinArrayBounds(x-1,y) And a(x-1,y) And closed(x-1,y)=0
    open(x-1,y)=1
  EndIf
  If withinArrayBounds(x,y-1) And a(x,y-1) And closed(x,y-1)=0
    open(x,y-1)=1
  EndIf
    If withinArrayBounds(x+1,y) And a(x+1,y) And closed(x+1,y)=0
    open(x+1,y)=1
  EndIf
    If withinArrayBounds(x,y+1) And a(x,y+1) And closed(x,y+1)=0
    open(x,y+1)=1
  EndIf
  closed(x,y)=1
  open(x,y)=0
EndProcedure

Procedure.b withinArrayBounds(x,y)
  If x>=0 And x<=xMax And y>=0 And y<=yMax
    ProcedureReturn 1
  Else
    ProcedureReturn 0
  EndIf
EndProcedure

Procedure showMap()
  For k=0 To yMax
    Print( Chr(177) )
  
    For i=0 To xMax
      Print( Str(a(i,k)) )
    Next
    Print( Chr(177) )
    
    
    For i=0 To xMax
      If a(i,k)
        Print("1")
      Else
        Print(" ")
      EndIf
    Next
    Print( Chr(177) )
    
    
    For i=0 To xMax
      If closed(i,k)
        Print("1")
      Else
        Print(" ")
      EndIf
    Next
    Print( Chr(177) )
    PrintN("")    
    
  Next
  PrintN("")
EndProcedure

ganz rechts erscheint dann die zuletzt verwendete closed liste, und wenn die leer ist, ist auch die map ganz rechts leer.

[ullmann]

Kleine Korrektur bei meinem Algorithmus nötig:

Das Feld das in die Liste "Fertig" geschrieben wurde muss auf Spalte=11 (nicht 12) getestet werden (da die Spalten von 0 bis 11 nummeriert sind).

Ein Weg liegt bereits vor, wenn ein Feld mit Spalte=11 in die offene Liste eingetragen werden soll.

Rainer