Resolución de laberintos con primera búsqueda de amplitud

Solución:

Aquí hay un solucionador completo de BFS Maze. Devuelve una ruta completa más corta hasta el punto final si se encuentra. En el laberinto arr: 0 denota espacios inexplorados, 5 es un espacio de pared, y 9 es el espacio de la meta. Los espacios están marcados con un -1 después de haber sido visitados.

import java.util.*;

public class Maze {

  public static int[][] arr = new int[][] {
            {0,0,0,0,0,0,0,0,0},
            {5,5,5,0,0,0,0,0,0},
            {0,0,0,5,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,9},
    };

  private static class Point {
        int x;
        int y;
        Point parent;

        public Point(int x, int y, Point parent) {
            this.x = x;
            this.y = y;
            this.parent = parent;
        }

        public Point getParent() {
            return this.parent;
        }

        public String toString() {
            return "x = " + x + " y = " + y;
        }
  }

  public static Queue<Point> q = new LinkedList<Point>();

    public static Point getPathBFS(int x, int y) {

        q.add(new Point(x,y, null));

        while(!q.isEmpty()) {
            Point p = q.remove();

            if (arr[p.x][p.y] == 9) {
                System.out.println("Exit is reached!");
                return p;
            }

            if(isFree(p.x+1,p.y)) {
                arr[p.x][p.y] = -1;
                Point nextP = new Point(p.x+1,p.y, p);
                q.add(nextP);
            }

            if(isFree(p.x-1,p.y)) {
                arr[p.x][p.y] = -1;
                Point nextP = new Point(p.x-1,p.y, p);
                q.add(nextP);
            }

            if(isFree(p.x,p.y+1)) {
                arr[p.x][p.y] = -1;
                Point nextP = new Point(p.x,p.y+1, p);
                q.add(nextP);
            }

             if(isFree(p.x,p.y-1)) {
                arr[p.x][p.y] = -1;
                Point nextP = new Point(p.x,p.y-1, p);
                q.add(nextP);
            }

        }
        return null;
    }


    public static boolean isFree(int x, int y) {
        if((x >= 0 && x < arr.length) && (y >= 0 && y < arr[x].length) && (arr[x][y] == 0 || arr[x][y] == 9)) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {

        Point p = getPathBFS(0,0);

         for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(arr[i][j]);
            }
            System.out.println();
        }

        while(p.getParent() != null) {
            System.out.println(p);
            p = p.getParent();
        }

    }

}

Respuesta corta: si

Explicación:

Ese pseudocódigo representa el camino a través del laberinto como un camino hacia la hoja de un árbol. Cada lugar en el laberinto es un nodo en el árbol y cada nuevo lugar al que puede ir desde allí es un hijo de ese nodo.

Para hacer una búsqueda de amplitud primero, un algoritmo primero tiene que considerar todas las rutas a través del árbol de longitud uno, luego de longitud dos, etc.hasta que llega al final, lo que hará que el algoritmo se detenga ya que el final no tiene hijos, lo que resulta en una cola vacía.

El código realiza un seguimiento de los nodos que necesita visitar mediante el uso de una cola (Q). Primero establece el inicio del laberinto en la raíz del árbol, lo visita (comprueba si es el final), luego elimina la raíz de la cola y repite el proceso con cada hijo. De esta manera, visita los nodos en orden posterior, es decir, root, (cada hijo de root), (cada hijo del primer hijo), (cada hijo del segundo hijo), etc. hasta que llega al final.

editar: Tal como está, el algoritmo puede no terminar cuando llega al final debido a otros nodos después de él en la cola. Tendrá que redactar la condición de despido usted mismo.

---

---

Utiliza Nuestro Buscador