title: GRAPH: find an algorithm to determine the shortest path from one point to another in a rectangular maze?
body: <p>I'm getting such an headache trying to elaborate an appropriate algorithm to go from a <strong>START</strong> position to a <strong>EXIT</strong> position in a maze. 
  For what is worth, the maze is <strong>rectangular</strong>, <strong>maxsize 500x500</strong> and, in theory, is resolvable by DFS with some branch and bound techniques ...</p>
  
  <pre><code>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
  </code></pre>
  
  <p>Explanation:<br>
  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".</p>
  
  <p>So, in the input <strong>10</strong> is the initial agent's energy, <strong>3 4</strong> is the <strong>START</strong> position (i.e. column 3, line 4) and we have a maze <strong>7x6</strong>. 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).</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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)....</p>
  
  <p>EDIT:</p>
  
  <p>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...</p>
  
  <pre><code>public class exitFromMaze {
  
      int energy, startY, startX, xMax, yMax;
      int adjMatrix[][];
      boolean visited[][];
      ArrayList&lt;Cell&gt; neighbours;
  
      //ArrayList&lt;Cell&gt; visited;
      Cell start;
      Stack&lt;Cell&gt; stack;
  
      public exM() {
          Scanner cin = new Scanner(System.in);
          int nrTests = cin.nextInt();
          for (int i = 0; i &lt; 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&lt;Cell&gt;();
              this.stack = new Stack&lt;Cell&gt;();
              for (int r = 0; r &lt; yMax; r++) { // yMax linhas
                  for (int c = 0; c &lt; 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 &amp;&amp; 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&lt;Cell&gt;) 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() &lt; this.energy &amp;&amp; !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 &lt; (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 &gt; 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 &gt; 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 &lt; (horizontalLimit - 1)) {
                  ret = new Cell(row , col+1, this);
              }
              return ret;
          }
  
          public List getNeighbours(int xlimit, int ylimit) {
              ArrayList&lt;Cell&gt; res = new ArrayList&lt;Cell&gt;(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 &lt; w; i++) {
              System.out.print("\t" + i);
          }
          System.out.println();
          for (int r = 0; r &lt; h; r++) {
              System.out.print("  " + r);
              for (int c = 0; c &lt; w; c++) {
                  System.out.print("\t" + adjMatrix[r][c]);
              }
              System.out.println("");
          }
          System.out.println();
      }
  
      public static void main(String args[]) {
          new exM();
      }
  }
  </code></pre>
  
  <p>For the input:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>It should print:</p>
  
  <pre><code>12 5 1 8 
  </code></pre>
  
  <p>i.e., the agent exit in a better exit, (0,4),with the a remaining energy= 12 and in only 8 steps.</p>
  
  <p>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...</p>
  
  <p>More inputs/outputs (when it's not possible to achieve an exit alive (with Energy>0), just print that fact).</p>
  
  <pre><code>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  
  </code></pre>