I just can not figure out how to search in width to find the shortest path in the maze. I can not deal with these queues, etc. Can anyone please help write the algorithm? Very urgent need

Here is the implementation of my search. The method takes two parameters as input - the coordinates of the starting point. In my case it is (2, 0). I can't deal with these queues. I want to first output the array to the console and display the shortest path there, and then, based on this, move the smiley in the maze using the same indices

public void findPath(int x,int y) { ArrayList<Pair<Integer,Integer>> queue = new ArrayList<Pair<Integer,Integer>>(); queue.add(new Pair<Integer,Integer>(x,y)); mas[x][y] = 1; while (queue.size() > 0) { Pair<Integer,Integer> cur = queue.remove(queue.size() - 1); // if (x < width - 1 && mas[x + 1][y] == 0) { queue.add(new Pair<Integer,Integer>(x+1, y)); mas[x+1][y] = 1; } if (x > 0 && mas[x - 1][y] == 0) { queue.add(new Pair<Integer,Integer>(x-1,y)); mas[x-1][y] = 1; } if (y < height - 1 && mas[x][y+1] == 0) { queue.add(new Pair<Integer,Integer>(x, y + 1)); mas[x][y+1] = 1; } if (y > 0 && mas[x][y-1] == 0) { queue.add(new Pair<Integer,Integer>(x, y - 1)); mas[x][y-1] = 1; } // } }
  • and what exactly is the problem? The algorithm is quite simple and well-known. - pavel
  • pavel I can not understand its implementation. Already reviewed all sites. I just can not understand how it can be applied in my maze so that the smiley from the set point reaches the exit. - anton.rynkovoy

1 answer 1

Clearly, you have a more or less correct search algorithm in width and you need to restore the path. I suggest doing this as a separate function, in fact, the mas array is more than enough to restore the answer, so I don’t see the point of my function. The function parameters are the end point. The path will be from the end, I think to deploy is not a problem.

 public void getPath(int x,int y){ while (mas[x][y] > 1){ System.out.println(x + " " + y); if (x < width - 1 && mas[x + 1][y] == mas[x][y] - 1) { x++; continue; } if (x > 0 && mas[x - 1][y] == mas[x][y] - 1) { x--; continue; } if (y < height - 1 && mas[x][y+1] == mas[x][y] - 1) { y++; continue; } if (y > 0 && mas[x][y-1] == mas[x][y] - 1) { y--; continue; } } System.out.println(x + " " + y); }
  • How to understand the restoration of the path? Collections do not need any in the algorithm? - anton.rynkovoy
  • Somehow I used to write "answer recovery" when you need not only a number in response, but also a plan how to get it. This is from dynamic programming gone. - pavel
  • @Rynkovoy Well, I output to the console, you think you will need to save. But this is the little things. - pavel
  • I do not need to save. ease to bring in the labyrinth the way) - anton.rynkovoy
  • Well, it outputs. - pavel