Finden Sie "Nummer" in einem 2d-Array

Question

Ich habe dieses Problem, das ich auf die effektivste Art und Weise lösen muss. Ich habe ein 2D-Array, das Folgendes enthält: Alles, was eine 1 ist, ist eine "Wand", was bedeutet, dass Sie nicht durchgehen können. 2 ist der Eingang, wo Sie das Array oder die Karte "betreten", wenn Sie möchten. 3 sind die Dinge, die wir finden müssen. Hier ist ein Beispiel einer Karte:

1111111 
1 3131 
2 11111 
1 31 
1111111 

Dies ist ein Beispiel eines Arrays sein könnte, die ich brauche, um aussehen Wie Sie sehen können gibt es eine 3 ist, die „nicht erreichbar, da es von einer Mauer umgeben ist“. .... 1" , was bedeutet, dass es zwei verfügbaren Zahlen in diesem Array

Zuerst haben wir den Eingang finden müssen Da der Eingang überall sein kann ich das gesamte Array suchen muss ich habe folgendes getan:

int treasureAmount = 0; 
    Point entrance = new Point(0,0); 
    for (int i = 0; i < N; i++) { 
     for (int j = 0; j < N; i++){ 
      if(map[i][j] == 2){ 
       entrance.x =i; 
       entrance.y =j; 
      } 

     } 

Dies dauert O (n^2) Zeit, und ich sehe nicht wirklich eine andere Möglichkeit, dies zu tun, seit Der Eingang kann überall sein. Allerdings bin ich nicht wirklich sicher, wie man die verfügbaren Nummern effektiv und schnell findet. Ich dachte darüber nach, während ich die Arrays nach dem Eingang suche, gleichzeitig finde ich die ganze Nummer 3 im Array, obwohl einige nicht zugänglich sein könnten, und danach bin ich nicht wirklich sicher, wie ich effektiv finde welche zugänglich sind.

Answer 1

Sie können es nicht besser machen, dass O (n^2). Es wird so lange dauern, das Array zu lesen. Aber dann könnten Sie eine Tiefensuche machen, um die erreichbaren 3's im Array zu finden. Hier ist der Pseudocode.

main() 
{ 
    read array and mark the entrance as ent.x and ent.y and also an array threex[] and threey[] that stores all the exit position. 
    boolean visited[][]; //stores whether array[i][j] is reachable or not. 
    dfs(ent.x,ent.y); 
    for each element in three arrays 
    { 
     if(visited[threex[i]][threey[i]]) print ("Reachable"); 
     else print("not reachable", threex[i], threey[i]); 
    } 
} 
int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; // dx[i], dy[i] tells whether to move in E,N,W,S respectively. 
dfs(int x,int y) 
{ 
    visited[x][y]=true; 
    for(i=0;i<4;i++)//move in all directions 
    { 
     int newx=x+dx[i],newy=y+dy[i]; 
     //check if this is within the array boundary 
     if(newx>=0&&newx<N && newy>=0&&newy<N) 
     if(!visited[newx][newy] && array[newx][newy]!=1) // check if the node is unvisited and that it is pemissible 
      dfs(newx,newy); 
    } 
} 

Da jedes Array-Element aufgenommen wird, nicht mehr als einmal in dem dfs funktionieren die Komplexität des Codes ist O (n^2).

Answer 2

Wenn Sie das Array erstellen, können Sie eine Liste von Koordinaten mit dem Wert 2 beibehalten. Sie können diese Liste in O (n) durchlaufen.

Answer 3

Da sowohl Eingangs- als auch Zielobjekte überall im Array sein können, haben Sie nicht viel Auswahl, sondern alles zu durchsuchen. Ihre Suche nach Einträgen ist also so effizient wie möglich, und in Bezug auf die Zielobjekte empfehle ich die maze flood fill algorithm.

Allerdings favorisiert die verknüpfte Version des Algorithmus eine Richtung (wie es mit Wasser gefüllt wird, es flutet "nach unten"). Um so effizient wie es kann, sollten Sie es in alle Richtungen machen erweitern (wie Sie es mit Gasfüllung), z.B .:

  2 
     1 212 
0 101 21012 
     1 212 
      2 

Die Zahlen stellen die Iterationen der Expansion. Die Erweiterung erfolgt in vier Richtungen: links, rechts, oben und unten. Wenn Sie das Zielobjekt erreichen, können Sie die kürzeste Route finden, indem Sie einfach zum benachbarten Zellennachbarn zurückkehren, dessen Iterationsindex um eins kleiner ist, bis Sie zum 0-Iterationsindex - dem Eingang - zurückkehren.