GRAPH: find an algorithm to determine the shortest path from one point to another in a rectangular maze?

Question

I'm getting such an headache trying to elaborate an appropriate algorithm to go from a START position to a EXIT position in a maze. For what is worth, the maze is rectangular, maxsize 500x500 and, in theory, is resolvable by DFS with some branch and bound techniques ...

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 looses energy every time he gives a step and he can only move UP, DOWN, LEFT and RIGHT. Also, if the agent arrives with a remaining energy of zero or less, he dies, so we print something like "Impossible".

So, in the input 10 is the initial agent's energy, 3 4 is the START position (i.e. column 3, line 4) and we have a maze 7x6. Think this as a kind of labyrinth, in which I want to find the exit that gives the agent a better remaining energy (shortest path).

In case there are paths which lead to the same remaining energy, we choose the one which has the small number of steps, of course.

I need to know if a DFS to a maze 500x500 in the worst case is feasible with these limitations and how to do it, storing the remaining energy in each step and the number of steps taken so far.

The output means the agent arrived with remaining energy= 5 to the exit pos 1 4 in 2 steps. If we look carefully, in this maze it's also possible to exit at pos 3 1 (column 3, row 1) with the same energy but with 3 steps, so we choose the better one.

With these in mind, can someone help me some code or pseudo-code? I have troubles working this around with a 2D array and how to store the remaining energy, the path (or number of steps taken)....

EDIT:

Larry, as I said, I'me a little bit confused about the code. Here's what I've tried so far, only to determine the shortest path with less steps from START to EXIT, fixing EXIT in the meanwhile...

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, startY, 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, int y, 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, col ,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();
    }
}

For the 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 

i.e., the agent exit in a better exit, (0,4),with the a remaining energy= 12 and in only 8 steps.

With my ideas, your help, is it ask to much to point me out my fails or correct them? I'm getting so sick of this ... because I gotta be complicating something easy...

More inputs/outputs (when it's not possible to achieve an exit alive (with Energy>0), just print that 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  

Answer 1

Just use Dijkstra's algorithm, using the implicit graph in the cardinal directions. Using the heap implementation it will be O(V log V), which should be good enough for 500x500. The first time you relax a node, it is with the lowest energy used you can get there. You can set up a node's precessor fairly trivially with this algorithm.

Edit: some pseudo code with explanation for 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.

That's the general pseudo code, though you would also have to keep track of the number of steps, mostly as a tiebreaker, so it shouldn't be too much more work.

As for the DFS solution, it depends on what the energy can be. If it is bounded, small, and an int, you can convert the 2D graph into a 3D graph on x-y-e, where e is the energy remaining - you start at the initial energy, and work your way down, but keeping track of places you've been before.

Edit: For the DFS solution, it should be O(H*W*E), for E <= 30000, H, W <= 500 it will not likely be fast enough, at least for real time, and might take a bit of memory.