Java – graph: find an algorithm to determine the shortest path from one point to another in a rectangular maze?
I am trying to work out an appropriate algorithm to move from the start position to the exit position in the maze
10 3 4 7 6 3 3 1 2 2 1 0 2 2 2 4 2 2 5 2 2 1 3 0 2 2 2 2 1 3 3 4 2 3 4 4 3 1 1 3 1 2 2 4 2 2 1 Output: 5 1 4 2
Explanation: our agent loses energy every step. He can only move up, down, left and right In addition, if the agent's residual energy is zero or less, he will die, so we print something like "impossible"
Therefore, input 10 is the energy of the initial agent, 3 and 4 are the start position (i.e. column 3, row 4), and we have a maze 7 × 6. Think of it as a maze, in which I want to find an exit for the agent to have better residual energy (shortest path)
If there is a path leading to the same residual energy, we certainly choose a path with a small number of steps
I need to know in the worst case DFS to maze 500 × 500 is feasible for these limitations and how to operate, store the remaining energy in each step and the number of steps taken so far
The output means that the agent reaches the exit position with residual energy = 5 and 4 in two steps If we observe carefully, in this maze, we can also exit position 31 (column 3, row 1) with the same energy but in three steps, so we choose the better one
With this in mind, can someone help me with some code or pseudo code? I have trouble using 2D arrays and how to store the remaining energy, path (or number of steps taken)
Edit:
Larry, as I said, I'm a little confused about the code This is what I have tried so far, just to determine the shortest path. There are fewer steps from start to exit, and repair exit
public class exitFromMaze {
int energy,startY,startX,xMax,yMax;
int adjMatrix[][];
boolean visited[][];
ArrayList<Cell> neighbours;
//ArrayList<Cell> visited;
Cell start;
Stack<Cell> stack;
public exM() {
Scanner cin = new Scanner(system.in);
int nrTests = cin.nextInt();
for (int i = 0; i < nrTests; i++) {
energy = cin.nextInt();
startY = cin.nextInt()-1; //start at columnstartY
startX = cin.nextInt()-1; //start at line startX
xMax = cin.nextInt();//7 cols
yMax = cin.nextInt(); //8 rows
adjMatrix = new int[yMax][xMax];
visited = new boolean[yMax][xMax];
//visited = new ArrayList<Cell>();
this.stack = new Stack<Cell>();
for (int r = 0; r < yMax; r++) { // yMax linhas
for (int c = 0; c < xMax; c++) { // xMax colunas
adjMatrix[r][c] = cin.nextInt();
visited[r][c] = false;
//System.out.println("matrix["+r+"]["+c+"] = "+adjMatrix[r][c]);
}
}
start= new Cell(startX,0);
//adiciona a pos actual à pilha de celulas/nos
stack.push(start);
//printArray(yMax,xMax);
findBestExit();
}//end_of_test_Cases
}
private void findBestExit() {
// BEGINNING OF DEPTH-FIRST SEARCH
Cell curCell;
while (!(stack.empty())) {
curCell = (Cell) (stack.pop());
//just fix an exit point ...for Now (if it works for one,it has to work for all the other possible exits)
if (curCell.row==0 && curCell.col== 4) {
System.out.println("Arrived at pos: "+curCell.row+","+curCell.col+" with E= "+(energy-curCell.getEnergy())+" with "+curCell.getSteps()+" steps");
//finish = curCell;
break;
} else {
visited[curCell.row][curCell.col] = true;
}
this.neighbours = (ArrayList<Cell>) curCell.getNeighbours(this.xMax,this.yMax);
for (Cell neighbourCell: neighbours) {
//1- I think something's missing here and it would be here the point to cut some cases...isn't it?
if ( curCell.getEnergy() + neighbourCell.getEnergy() < this.energy && !visited[neighbourCell.row][neighbourCell.col]){
neighbourCell.energy+= curCell.energy;
neighbourCell.setSteps(curCell.getSteps()+1);
neighbourCell.setPrevIoUs(curCell);
stack.push(neighbourCell);
}
// ...
}
}
// END OF DEPTH-FIRST SEARCH and DIJKSTRA?
}
class Cell {
int row;
int col;
int energy;
int steps;
Cell prevIoUs;
//Node next;
public Cell(int x,int y,int steps) {
this.row = x;
this.col = y;
this.energy = adjMatrix[x][y];
this.steps = steps;
//this.next = null;
this.prevIoUs = null;
}
public Cell(int x,Cell prev) {
this.row = x;
this.col = y;
this.steps = 0;
this.energy = adjMatrix[x][y];
this.prevIoUs = prev;
}
@Override
public String toString() {
return "(,"+this.getRow()+","+this.getCol()+")";
}
public int getEnergy() {
return energy;
}
public void setEnergy(int energy) {
this.energy = energy;
}
public Cell getPrevIoUs() {
return prevIoUs;
}
public void setPrevIoUs(Cell prevIoUs) {
this.prevIoUs = prevIoUs;
}
public int getRow() {
return row;
}
public void setRow(int x) {
this.row = x;
}
public int getCol() {
return col;
}
public void setCol(int y) {
this.col = y;
}
public int getSteps() {
return steps;
}
public void setSteps(int steps) {
this.steps = steps;
}
public Cell south(int verticalLimit) {
Cell ret = null;
if (row < (verticalLimit - 1)) {
ret = new Cell(row+1,col,this);
//ret.prevIoUs = this;
}
return ret;
}
/**
* Gives the north to our current Cell
* @return the Cell in that direction,null if it's impossible
* to go in that direction
*/
public Cell north() {
Cell ret = null;
if (row > 0) {
ret = new Cell(row-1,this);
//ret.prevIoUs = this;
}
return ret;
}
/**
* Gives the west (left) to our current Cell
* @return the Cell in that direction,null if it's
* impossible to go in that direction
*/
public Cell west() {
Cell ret = null;
if (col > 0) {
ret = new Cell(row,col-1,this);
//ret.prevIoUs = this;
}
return ret;
}
/**
* Gives the east direction(right) to our current Cell
* @return the Cell in that direction,null if it's
* impossible to go in that direction
*/
public Cell east(int horizontalLimit) {
Cell ret = null;
//if it's inside the number max of collumns
if (col < (horizontalLimit - 1)) {
ret = new Cell(row,col+1,this);
}
return ret;
}
public List getNeighbours(int xlimit,int ylimit) {
ArrayList<Cell> res = new ArrayList<Cell>(4);
Cell n;
n = south(ylimit);
if (n != null) {
res.add(n);
}
n = north();
if (n != null) {
res.add(n);
}
n = east(xlimit);
if (n != null) {
res.add(n);
}
n = west();
if (n != null) {
res.add(n);
}
return res;
}
}
private void printArray(int h,int w) {
int i,j;
// print array in rectangular form
System.out.print(" ");
for (i = 0; i < w; i++) {
System.out.print("\t" + i);
}
System.out.println();
for (int r = 0; r < h; r++) {
System.out.print(" " + r);
for (int c = 0; c < w; c++) {
System.out.print("\t" + adjMatrix[r][c]);
}
System.out.println("");
}
System.out.println();
}
public static void main(String args[]) {
new exM();
}
}
Input:
1 40 3 3 7 8 12 11 12 11 3 12 12 12 11 11 12 2 1 13 11 11 12 2 13 2 14 10 11 13 3 2 1 12 10 11 13 13 11 12 13 12 12 11 13 11 13 12 13 12 12 11 11 11 11 13 13 10 10 13 11 12
It should print:
12 5 1 8
That is, the agent leaves with a better outlet (0,4), residual energy = 12 and only 8 steps
With my ideas and your help, do you ask me to point out my failures or correct them? I'm tired of it... Because I want to make things simple
More input / output (when exit cannot be achieved (energy > 0), just print the fact)
3 40 3 3 7 8 12 11 12 11 3 12 12 12 11 11 12 2 1 13 11 11 12 2 13 2 14 10 11 13 3 2 1 12 10 11 13 13 11 12 13 12 12 11 13 11 13 12 13 12 12 11 11 11 11 13 13 10 10 13 11 12 8 3 4 7 6 4 3 3 2 2 3 2 2 5 2 2 2 3 3 2 1 2 2 3 2 2 4 3 3 2 2 4 1 3 1 4 3 2 3 1 2 2 3 3 0 3 4 10 3 4 7 6 3 3 1 2 2 1 0 2 2 2 4 2 2 5 2 2 1 3 0 2 2 2 2 1 3 3 4 2 3 4 4 3 1 1 3 1 2 2 4 2 2 1 Output 12 5 1 8 Goodbye cruel world! 5 1 4 2
Solution
Just use Dijkstra's algorithm and use the implicit chart of the main direction Using the heap implementation, it will be o (V log V) for 500 × 500 should be good enough The first time you relax a node, it uses the lowest energy and you can get there You can use this algorithm to set the precursor of a node quite simply
Edit: some pseudo codes to explain Dijkstra's algorithm:
function Dijkstra( graph,source ):
// distance is infinity to everywhere initially
dist = initialize list of size V to infinity
// no vertices pointed to anything
prevIoUs = initialize list of size V to undefined
// distance from source to source is 0
dist[source] = 0
Q = priority queue
insert all vertices into Q
while Q is not empty:
// get the vertex closest to the source
current_vertex = Q.pop
if dist[current_vertex] == infinity
break
// these are the adjacent vertices in the four cardinal direction
for each vertex next to current_vertex:
// if it costs less energy to go to vertex
// from current_vertex
if ( dist[current_vertex] + energy[vertex] < dist[vertex] )
dist[vertex] = dist[current_vertex] + energy[vertex]
prevIoUs[vertex] = current_vertex
// Another if statement here to
// minimize steps if energy is the same
// Now after this is done,you should have the cheapest cost to
// each vertex in "dist". Take the cheapest one on the edge.
// You can walk backwards on the "prevIoUs" to reconstruct the path taken.
This is general pseudo code, although you must also track the number of steps, mainly as a decisive game, so it shouldn't be too much work
As for DFS solution, it depends on the energy If it's bounded, small, and an int, you can convert 2D graphics to 3D graphics on XYE, where e is the remaining energy - you start with the initial energy and then work down, but track where you've been
Editor: for DFS solution, it should be o (h * w * e). For e < = 30000, h, w < = 500, it cannot be fast enough, at least for real-time, and it may need some memory