Felder,Ketten im Array finden

[Periander]

Hallo,

schwierig zu formulieren, was für einen algorithmus ich gerade versuche zu bauen.
es geht um folgendes:

ich habe ein array einer beliebigen größe.
dadrin sind verschiedene zahlenwerte.
mein beispiel hier hat zur veranschaulichung nur die einträge "x" und "_"

|x|x|x|_|x|_|
|_|x|x|_|x|_|
|_|_|x|x|x|_|
|_|_|x|_|_|_|
|x|x|x|_|x|x|

ich will jetzt die zusammenhängenden felder identifizieren, wenn ich mir also die obere linke ecke anschaue, dann
will ich als ergebniss das gesamte zusammenhänge feld, von hier 14 "x"en. und wenn ich mir die untere rechte ecke
anschaue nur ein feld bestehend aus 2 "x"en.

zusammenhängend ist so eine kette wenn entweder oben/unten oder links/rechts ein weiteres "x" kommt.
also schräg zählt nicht.

bisher ist es mir nicht gelungen da was gescheites zu finden.
wenn ich zuerst schaue ob von meinem feld ausgehend rechts/links/oben/unten ein weiteres "x" kommt ist das
zwar ein guter ansatz, aber dann wird das relativ kompliziert, wenn dann ein ergebnis mehrere anliegende positionen liefert...

hat von euch einer eine idee, wie man das lösen kann ohne ein buch mit lauter "if" anweisungen zu schreiben?

[patti]

Lösung heißt Rekursion (in Zusammenhang mit dem Stichwort Backtracking) und lässt sich so z.B. in FloodFill-Algorithmen finden. Einfach mal danach googeln ;)

[DeddyH]

Da gab es doch was von Chäffe: http://www.delphipraxis.net/71684-ti...lclimbing.html

[Periander]

super, klingt alles schonmal vielversprechend.
werd mich mal schlau machen,

danke schonmal.

[Bummi]

kleines demo

Delphi-Quellcode:

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Grids, StdCtrls;

type
  TInfoRec=Record
    Sign:String;
    Visited:Boolean;
  End;
  TInfoRecArray =Array of Array of TInfoRec;

  TForm1 = class(TForm)
    Button1: TButton;
    g: TStringGrid;
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
    FArray:TInfoRecArray;
    FFound:Integer;
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

Function Count4Sign(arr:TInfoRecArray;const s:String;x,y:Integer):Integer;
begin
  Result := 0;
  if (x>=0) and (y>=0) and (x<=High(arr)) and (y<=High(arr[0]))then
       if (arr[x,y].Sign = s) and not (arr[x,y].Visited) then
        begin
        Result := 1;
        arr[x,y].Visited := true;
        end;
  if Result=1 then
    begin
    Result := Result + Count4Sign(arr,s,x + 1,y);
    Result := Result + Count4Sign(arr,s,x - 1,y);
    Result := Result + Count4Sign(arr,s,x,y + 1);
    Result := Result + Count4Sign(arr,s,x,y - 1);
    end;


end;

procedure TForm1.Button1Click(Sender: TObject);
var
  x,y:Integer;
  sign:String;
begin
  SetLength(FArray,g.ColCount,g.RowCount);
  sign :=   g.Cells[g.Col,g.Row];
  For X := 0 to g.ColCount - 1 do
    For Y := 0 to g.RowCount - 1 do
    begin
       FArray[x,y].Sign := g.Cells[x,y];
       FArray[x,y].Visited := false;
    end;
  FFound := Count4Sign(FArray,sign,g.Col,g.Row);
  Caption := IntToStr(FFound);
end;

[patti]

Hab da gerade mal was zusammengetippt. Ist allerdings in Java, da ich im Moment keine Delphi-Umgebung bei der Hand habe. Vielleicht hilft dir das ja schonmal einbisschen weiter ;)

(Hoffe, dass ich keinen Fehler mehr drin habe, aber bei meinen Tests lief alles gut ;) )

Code:

public class KettenFinden {
   public static void main(String[] args) {
      int[][] feld = new int[5][10];
      //
      fill(feld);
      //
      System.out.println("Ausgangsfeld:\n");
      print(feld);
      //
      System.out.println("\n********************\n");
      //
      final int x = 0;
      final int y = 0;
      //
      System.out.format("Kette für x = %d, y = %d:\n",x,y);
      //
      findeKette(feld,x,y);
   }
   
   public static void print(int[][] feld) {
      for (int x = 0; x < feld.length; x++) {
         for (int y = 0; y < feld[x].length; y++) System.out.print("|"+feld[x][y]+"|");
         System.out.println();
         for (int y = 0; y < feld[x].length; y++) System.out.print("---");
         System.out.println();
      }
   }

   public static void fill(int[][] feld) {
      for (int x = 0; x < feld.length; x++)
         for (int y = 0; y < feld[x].length; y++)
            feld[x][y] = (int)(Math.random() * 3);
   }

   public static void findeKette(int[][] feld, int x, int y) {
      if (x >= 0 && x < feld.length && y >= 0 && y < feld[0].length) {
         boolean[][] besucht = new boolean[feld.length][feld[0].length];
         //
         helper(feld,besucht,x,y);
         //
         for (int i = 0; i < besucht.length; i++) {
            for (int j = 0; j < besucht[i].length; j++) System.out.print("|" + (besucht[i][j] ? "x" : " ") + "|");
            System.out.println();
            for (int j = 0; j < besucht[i].length; j++) System.out.print("---");
            System.out.println();
         }
      }
   }

   private static void helper(int[][] feld, boolean[][] besucht, int x, int y) {
      besucht[x][y] = true;
      //
      if (x-1 >= 0 && !besucht[x-1][y] && feld[x-1][y] == feld[x][y]) helper(feld,besucht,x-1,y);
      if (y-1 >= 0 && !besucht[x][y-1] && feld[x][y-1] == feld[x][y]) helper(feld,besucht,x,y-1);
      if (x+1 < feld.length && !besucht[x+1][y] && feld[x+1][y] == feld[x][y]) helper(feld,besucht,x+1,y);
      if (y+1 < feld[x].length && !besucht[x][y+1] && feld[x][y+1] == feld[x][y]) helper(feld,besucht,x,y+1);
   }
}

Beispiel-Ausgabe:

Code:

Ausgangsfeld:

|1||1||0||2||1||2||2||1||0||0|
------------------------------
|1||1||0||0||2||0||0||0||2||2|
------------------------------
|0||1||2||0||1||2||0||1||2||2|
------------------------------
|1||0||2||2||1||1||0||1||1||2|
------------------------------
|0||2||1||2||1||2||2||2||1||0|
------------------------------

********************

Kette für x = 0, y = 0:

|x||x|| || || || || || || || |
------------------------------
|x||x|| || || || || || || || |
------------------------------
| ||x|| || || || || || || || |
------------------------------
| || || || || || || || || || |
------------------------------
| || || || || || || || || || |
------------------------------

Grüße,
Patrick


EDIT:
Hm, da war ich wohl nicht der einzige, der helfen wollte ;) Naja, jetzt hast du sogar zwei Lösungen in zwei verschiedenen Programmiersprachen, was will man mehr? :stupid:

EDIT2:
Gibts hier eigentlich eine Möglichkeit zum Highlighten von Java-Quellcode?

[BoolString]

Ich glaube das gesuchte Stichwort ist der Hoshen-Kopelman Algorithmus.

Unter: http://www.ocf.berkeley.edu/~fricke/...nkopelman.html
findet sich ein Einstieg. Ist auf jeden Fall gut nachvollziehbar.

Das entsprechende Paper ist bibliographisch verortet unter:
J. Hoshen & R. Kopelman (1976) 'Percolation and cluster distribution. I. Cluster multiple labeling technique and critical concentration algorithm', Phys. Rev. B. 1(14):3438-3445 (http://prb.aps.org/abstract/PRB/v14/i8/p3438_1)

Ich muss mal schauen, irgendwo hab ich so was vor Jahren mal gebastelt. Ich find es nur gerade nicht mehr...

Jan