使用广度优先搜索算法存储迷宫求解的路径。

go评论64阅读模式

Store the path for maze solving using Breadth First Search Algorithm

问题

``````import java.util.ArrayList;

public class Square {
private int x;
private int y;
private int distance;

public Square(int x, int y, int distance) {
this.x = x;
this.y = y;
this.distance = distance;
}

public int getX() {
return x;
}

public int getY() {
return y;
}

public int getDistance() {
return distance;
}
}

public class ArrayQueue<T> {
// Queue implementation
// ...
}

public class BreathAlgorithm {
// Algorithm implementation
// ...
}

public class MazeRunner {
// MazeRunner class implementation
// ...
}
``````

Note: The provided code contains complex logic for maze traversal and pathfinding. The code includes the definitions of various classes and methods like `Square`, `ArrayQueue`, `BreathAlgorithm`, and `MazeRunner`. If you have specific questions or need assistance with certain parts of the code, please feel free to ask.

I am using Breadth First Search Algorithm to solve a maze. My algorithm successfully finds the shortest path but it doesn't store the shortest path. It just tells me the number of steps used to complete this path but saves all the squares that have been checked no matter if they belong to the shortest path or not. I really tried quite a few ways to store the shortest path but I'm getting errors with the path where squares that are not in the shortest path are also included. If you could find me a way to store the shortest path in an ArrayList<Square> or ArrayQueue<Square> or array or anything. The correctPath() is what i did so i can decide which squares are in the shortest path but it's wrong. I dont think that is so complicated just i cannot figure out how to do it. Thanks for your time.

Squares have as attributes a x and y position and also the distance from the destination.

``````public class BreathAlgorithm {
// Java program to find the shortest path between a given source cell to a destination cell.
static int ROW;
static int COL;
// These arrays are used to get row and column numbers of 4 neighbours of a given cell
static int[] rowNum = {-1, 0, 0, 1};
static int[] colNum = {0, -1, 1, 0};

// check whether given cell (row, col) is a valid cell or not.
static boolean isValid(int row, int col)
{
// return true if row number and column number is in range
return (row &gt; 0) &amp;&amp; (row &lt;= ROW) &amp;&amp; (col &gt; 0) &amp;&amp; (col &lt;= COL);
}

// Checks if a square is an adjacent to another square
static boolean isNearSquare(Square a,Square b){
int x = 1;
int y = 0;
if((Math.abs((a.getX()+x) - (b.getX()+x))) + (Math.abs((a.getY()+y) - (b.getY()+y))) != 1){
return false;
}
x = -1;
y = 0;
if((Math.abs((a.getX()+x) - (b.getX()+x))) + (Math.abs((a.getY()+y) - (b.getY()+y))) != 1){
return false;
}
x = 0;
y = 1;
if((Math.abs((a.getX()+x) - (b.getX()+x))) + (Math.abs((a.getY()+y) - (b.getY()+y))) != 1){
return false;
}
x = 0;
y = -1;
return (Math.abs((a.getX() + x) - (b.getX() + x))) + (Math.abs((a.getY() + y) - (b.getY() + y))) == 1;
}

// returns the Square of the ending position
public static Square findEnd(int[][] mat){
for (int i=0;i&lt;mat.length;i++){
for(int j=0;j&lt;mat[0].length;j++){
if(mat[i][j] == 9)
return new Square(i,j,0);
}
}
return new Square(1,1,0);
}

/*
In this method i tried to define which squares are to be deleted from the fullPath
and return a new path with only the squares who are actually used in the shortest path.
This method doesn&#39;t work for all examples it just works for some so i guess it is lacking.
*/
public static ArrayQueue&lt;Square&gt; correctPath(ArrayList&lt;Square&gt; path) throws QueueFullException {
int i=0;
while(i&lt;path.size()-1){
if (path.get(i).getDistance() == path.get(i+1).getDistance()){
if (path.get(i+2)!=null &amp;&amp; path.get(i-1)!=null &amp;&amp; (!isNearSquare(path.get(i),path.get(i+2)) || !isNearSquare(path.get(i),path.get(i+2)))){
path.remove(i);
}
else if (path.get(i+2)!=null &amp;&amp; path.get(i-1)!=null &amp;&amp; (!isNearSquare(path.get(i+1),path.get(i-1)) || !isNearSquare(path.get(i+1),path.get(i+2)))){
path.remove(i+1);
}
else if (!isNearSquare(path.get(i),path.get(i+1))){
path.remove(i);
}
}
i++;
}
ArrayQueue&lt;Square&gt; correctPath = new ArrayQueue&lt;&gt;(path.size());
while(i&gt;=0){
correctPath.enqueue(path.get(i));
i--;
}
return correctPath;
}

static void printCorrectPath(ArrayQueue&lt;Square&gt; correctPath) throws QueueEmptyException {
Square[] originalPath = new Square[correctPath.size()];
for(int i=originalPath.length-1;i&gt;=0;i--){
originalPath[i] = correctPath.dequeue();
}
int i=0;
while(i&lt;originalPath.length-1){
if(i == 0) System.out.println(originalPath[i]+&quot; is the starting point.&quot;);
System.out.println(&quot;From &quot;+originalPath[i]+&quot;to &quot;+originalPath[i+1]);
i++;
if(i == originalPath.length-1) System.out.println(originalPath[i]+&quot; is the ending point.&quot;);
}
}

public static void searchPath(int[][] mat,Square start) throws QueueEmptyException, QueueFullException {
//mat is the maze where 1 represents a wall,0 represent a valid square and 9 is the destination
// When a square is visited from 0 it becomes a 2
ROW=mat.length;
COL=mat[0].length;
Square dest = findEnd(mat);         // search for the number 9 and make a new Square and put it in dest
int dist = BFS(mat, start, dest);   // find the least distance
if (dist != Integer.MAX_VALUE)
System.out.println(&quot;\nShortest Path is &quot; + dist+&quot; steps.&quot;);
else
System.out.println(&quot;Shortest Path doesn&#39;t exist&quot;);
}

// function to find the shortest path between a given source cell to a destination cell.
static int BFS(int[][] mat, Square src, Square dest) throws QueueFullException, QueueEmptyException {
ArrayList&lt;Square&gt; fullPath = new ArrayList&lt;&gt;();                // path of all the squares checked
boolean [][]visited = new boolean[ROW][COL];                   // if a square is visited then visited[x][y] = true
ArrayQueue&lt;Square&gt; q = new ArrayQueue&lt;&gt;(mat.length*mat[0].length);      // Create a queue for BFS
// check source and destination cell of the matrix have value 1
if (mat[src.getY()][src.getX()] != 0 || mat[dest.getX()][dest.getY()] != 9) {
return -1;
}
mat[src.getY()][src.getX()] = 2;                // Mark the source cell as visited
visited[src.getX()][src.getY()] = true;
q.enqueue(src);                                 // Enqueue source cell
while (!q.isEmpty())                            // Do a BFS starting from source cell
{
Square curr = q.front();
if (curr.getX() == dest.getX() &amp;&amp; curr.getY() == dest.getY()) {     // If we have reached the destination cell we are done
printCorrectPath(correctPath(fullPath));
return curr.getDistance();
}
q.dequeue();            // Otherwise dequeue the front cell in the queue and enqueue its adjacent cells
for (int i = 0; i &lt; 4; i++){
int row = curr.getX() + rowNum[i];
int col = curr.getY() + colNum[i];
// if adjacent cell is valid, has path and not visited yet, enqueue it.
if (isValid(row, col) &amp;&amp; mat[row][col] == 0 || mat[row][col] == 9 &amp;&amp; !visited[row][col]){
mat[row][col] = 2;
visited[row][col] = true;       // mark cell as visited and enqueue it
Square Adjcell = new Square(row,col, curr.getDistance() + 1 );
}
}
}
return -1;       // Return -1 if destination cannot be reached
}
``````

}

Here is the class where i do the testings.

``````public class MazeRunner {

// Maze is a 2d array and it has to be filled with walls peripherally
// with walls so this algorithm can work. Our starting position in this
// will be (1,1) and our destination will be flagged with a 9 which in
// this occasion is (11,8).
private int[][] maze ;
private final List&lt;Integer&gt; path = new ArrayList&lt;&gt;();
public long startTime,stopTime;

public MazeRunner(int [][] maze){
this.maze = maze;
}

public void runBFSAlgorithm(int startingX,int startingY) throws QueueEmptyException, QueueFullException {
startTime = System.nanoTime();
BreathAlgorithm.searchPath(maze,new Square(startingX,startingY,0));
stopTime = System.nanoTime();
System.out.printf(&quot;Time for Breath First Algorithm: %.5f milliseconds.\n&quot;,(stopTime-startTime)*10e-6);
}

public void printMaze(){
for (int[] ints : maze) {
for (int anInt : ints) {
System.out.print(anInt + &quot; &quot;);
}
System.out.println();
}
}

public static void main(String[] args) throws FileNotFoundException, QueueEmptyException, QueueFullException {
int [][] maze = {{1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,1,0,1,0,1,0,0,0,0,0,1},
{1,0,1,0,0,0,1,0,1,1,1,0,1},
{1,0,0,0,1,1,1,0,0,0,0,0,1},
{1,0,1,0,0,0,0,0,1,1,1,0,1},
{1,0,1,0,1,1,1,0,1,0,0,0,1},
{1,0,1,0,1,0,0,0,1,1,1,0,1},
{1,0,1,0,1,1,1,0,1,0,1,0,1},
{1,0,0,0,0,0,0,0,0,0,1,9,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1}};
int[] startingPoint = {1,1};
MazeRunner p = new MazeRunner(maze);
p.printMaze();
p.runBFSAlgorithm(startingPoint[0],startingPoint[1]);
}
``````

}

My execution would look like this:

The execution output

答案1

`Square`类的一个实例添加一个额外的属性：`Square cameFrom;`

``````q.enqueue(Adjcell);
``````

``````Adjcell.cameFrom = curr;
``````

Give an instance of `Square` an extra property: `Square cameFrom;`.

``````q.enqueue(Adjcell);
``````

to:

``````Adjcell.cameFrom = curr;
``````

Then, change `correctPath` so it takes `dest` as argument and builds the path as an `ArrayList&lt;Square&gt;` from following the linked list formed by the `cameFrom` property.

This list will then just need to be reversed to get it in the right order.

• 本文由 发表于 2020年10月7日 17:04:06
• 转载请务必保留本文链接：https://go.coder-hub.com/64240760.html
• algorithm
• arraylist
• java
• maze

go 66

go 77

go 81

go 59