Felder,Ketten im Array finden

[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?

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