x,y er koodinatet du starter på this.rows og this.cols er matricens max størrelse - kanten om man vil this.list er et array af arrays som holder de pladser som ER fundet. jeg har lavet en prototype funktion på Array som hedder find() -- lav en funktion som kigger dit array igennem om den plads du kigger efter allerede eksistere.
så hvidt jeg husker, lægger jeg det første element i this.list inden jeg går igang, dette for at initialiere den "farve" jeg kigger efter.
Som jeg læser det (jeg er ikke nogen ørn til Java), så finder din funktion sammenhængende blokke af samme værdi. Det kan jeg godt bruge, men det løser ikke mit problem:
Da jeg skal finde øer, som er omkranset af blokke med samme værdi, er jeg nødt til at have diagonalerne med. Det kan din funtion så godt udvides med, men der skal skelnes mellem diagonalerne (ja, faktisk også de regulære naboer), da ikke alle har relevans.
Her er et udsnit af det eksempel jeg viser i ovenstående link -Jeg har erstattet de relevante nuller med #, og de ikke-relevante med @:
En funktion som din (med diagonaler) ville finde alle # og @. Hvordan skelner jeg nu imellem dem? Og hvordan finder jeg ud af om det er et "lukket" område?
med en opgraderet version, som tjekker på diagonaler, skal du blot lave din "find" funktion om, sådan at den tjekke på 'linie-bredden' ... fx er disse næppe med på en linie: ## ##
man skal derfor se, om det felt du tjekke på vil gøre linien "fed" eller fortsætte den
## #? <-- false
###? <-- true
## # ? <-- true
osv....
Jeg tror man kan bruge euklid til at finde ø'er i en matrice... med distance vektorer... det er lidt langhåret.. og du kommer nok længst ved at lave "find" algoritmen sådan at man tjekke på om man er gået i ring...
Umiddelbart forestiller jeg mig problemets løsning sådan her:
Du har et array du looper igennem alle elementer i. Når du finder et match til en given værdi tilføjer du koordinatet til et array (eller en stak, eller hvad du nu ender med at bruge), og kalder en hjælpemetode.
Hjælpemetoden looper alle naboer igennem, dog springer den over det element vi fandt umiddelbart før det aktuelle (så går vi ikke i en uendelig løkke, og finder ikke startpositionen allerførste gang). Når den finder et match, tilføjer den koordinatet til et array hvis det er forskelligt fra startpositionen. Hvis det er det samme som startpositionen, så har du en ø. Finder du intet match, fjerner du det aktuelle punkt og går et trin tilbage (ved at returnere).
OK, jeg kan godt se en skitse til en løsning nu. Nu skal det bare kodes ;) Det kan godt tage lidt tid, så jeg vender måske tilbage med uddybende spørgsmål.
hvis man som pidgeot, vil kigge med look-ahead og look-behind, er man næsten nødt til at oprette et nyt array hver gang man finder et "T-kryds", så kalder man rekursivt for hver ny vej man går - og den/de veje som resultere i en ring, returneres... hvilket kan blive lidt af et problem :)
Bruger man eks. en stak som grundlag (hvilket jeg nævner som en mulighed), undgår man flere arrays ved hjælp af korrekt brug af push og pop - man kan blot sende stakken med som en reference, og dermed undgå en hel masse arrays der skal oprettes. Da det er .NET, har man endda en Stack-klasse klar i forvejen (System.Collections.Stack), og kan blot kalde ToArray når man har et match.
Ved at gemme hvor i "naboløkken" man er nået til sammen med positionen for punktet, er man endda rigtigt godt på vej til at have lavet den om til en iterativ løsning - men det er lidt nemmere at forklare tankegangen til dette problem ved at udtrykke det rekursivt.
Man skal naturligvis kunne håndtere dubletter på en eller anden måde, men det kan jeg ikke se man kommer udenom under alle omstændigheder.
Det eneste man "mangler" ift. .NET's egen Stack er muligheden for at se det element der kom på som det første - men det kan man jo håndtere på mange måder, også uden at skulle pille ved Stack'en.
Hej igen. Så har fået jeg lavet en funtion, den kunne sikkert være kortere og smartere, men den virker. Jeg har dog stadig et enkelt problem mht at identificere øen, (dvs når rekursen når tilbage til startcellen). Som det er nu har jeg lavet en tæller, jeg forlanger skal være >8 (Max antal naboer=0), men det er ikke optimalt da der kan være øer så små som 4 celler: # #0# #
Nogen ideer (med udgangspunkt i nedenstående)?
Private Sub FindFirstBlock()
Dim Block As New List(Of Point) Dim i, j As Integer For j = 0 To 9 For i = 0 To 9 If OrgMatrix(i, j) = 0 Then FirstCell = New Point(i, j) If Not Block Is Nothing Then Block.Clear() Block.Add(New Point(i, j)) BlockFound = False Count = 0 Call FindNeighbours(i, j, Block) If BlockFound Then Exit For End If Next i If BlockFound Then Exit For Next j
End Sub
OrgMatrix, FirstCell, Count og BlockFound er erklæret på modulniveau
Private Sub FindNeighbours(ByVal x As Integer, ByVal y As Integer, ByRef pList As List(Of Point))
Dim iMaxX As Integer = OrgMatrix.GetUpperBound(0) Dim iMaxY As Integer = OrgMatrix.GetUpperBound(1) Dim pNewPoint As Point Dim bExists As Boolean = False Count += 1 If x > 0 And y > 0 Then pNewPoint = New Point(x - 1, y - 1) If Not pNewPoint = FirstCell Then bExists = False If OrgMatrix(x - 1, y - 1) = 0 Then ' Tjek om den er på listen i forvejen: For Each aPoint As Point In pList If pNewPoint = aPoint Then bExists = True Exit For End If Next aPoint If Not bExists Then ' Tilføj til listen ,rekurser: pList.Add(New Point(x - 1, y - 1)) Call FindNeighbours(x - 1, y - 1, pList) End If End If Else ' Vi er tilbage ved den første celle: If Count > 8 Then BlockFound = True Exit Sub End If End If End If
******Her følger 7 If-blokke magen til ovenstående, der finder de andre naboer.
End Sub
Jeg mangler så blot at identificere 'falske' celler, samt cellerne inden i øen, men det er detaljer, der sagtens kan laves.
Jeg fik selv løst det sidste problem ved at læse pidgeots første kommentar: "dog springer den over det element vi fandt umiddelbart før det aktuelle"
Så nu ser funktionen sådan ud:
(Med PreviousCell erklæret på modulniveau)
Private Sub FindNeighbours(ByVal x As Integer, ByVal y As Integer, ByRef pList As List(Of Point))
Dim iMaxX As Integer = OrgMatrix.GetUpperBound(0) Dim iMaxY As Integer = OrgMatrix.GetUpperBound(1) Dim pNewPoint As Point Dim bExists As Boolean = False If x > 0 And y > 0 Then pNewPoint = New Point(x - 1, y - 1) If Not pNewPoint = PreviousCell Then If Not pNewPoint = FirstCell Then bExists = False If OrgMatrix(x - 1, y - 1) = 0 Then ' Tjek om den er på listen i forvejen: For Each aPoint As Point In pList If pNewPoint = aPoint Then bExists = True Exit For End If Next aPoint If Not bExists Then ' Tilføj til listen ,rekurser: PreviousCell = pList.Item(pList.Count - 1) pList.Add(New Point(x - 1, y - 1)) Call FindNeighbours(x - 1, y - 1, pList)
End If End If Else ' Vi er tilbage ved den første celle: BlockFound = True Exit Sub End If End If End If
******Her følger 7 If-blokke magen til ovenstående, der finder de andre naboer.
End Sub
I skal begge have tak for hjælpen, jeg kan selv komme videre herfra. Jeg har taget kraftigt udgangspunkt i montagos funktion, så jeg synes han skal have de fleste points, men pidgeot var i høj grad medvirkende, så vil du lægge et svar pidgeot?
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.
Ny bruger
Nybegynder
Opret
Preview
