GRAPH PROBLEM: find an algorithm to determine the shortest path from one point to another in a recta
- by newba
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)....
