[matteas]

Hello,
I'm stuck with my assignment and I would need some kind of a hint.

I have a 2D array with squares of different values. I'm supposed to get from a starting point (given) to a destination point (given) using the squares with the lowest value (values are counted using a function) and count the number of steps it took. If I reach a dead end, I have to go one or more steps back and try a different route. I can step on each tile only once. I have a working algorithm, but it doesn't seem to work with huge arrays. I believe I'm supposed to use a stack and I thought that my implementation was a stack, but I'm probably wrong.

My current solution is that I always store all adjacent squares in a 2D array (in a line, 2D because I need two coordinates

int[][] stack = new int[8000000][2];

), sorted by their values, and move to the next square and do the same again. I have another array (2D representation of the board) with boolean values telling me whether I have stepped on the square or not

boolean[][] visitedBool = new boolean[m][n];

. When I reach a dead end, I go back through the array until I reach a square that has not been visited yet and try going that way. This process is repeated until the point of destination is reached. However, this solution seems to be too slow.

Could you give me a hint what I need to do to make it faster?

[Dogstopper]

macosxnerd101 wrote a simply excellent article on backtracking here. However, you're right, with super large arrays, it can take a LOOOONG time.

Have you considered starting at the end and working your way back instead? It MIGHT take less time to do so based on the structure of that particular maze.

[matteas]

Dogstopper, on 12 March 2012 - 06:38 AM, said:

macosxnerd101 wrote a simply excellent article on backtracking here. However, you're right, with super large arrays, it can take a LOOOONG time.

Have you considered starting at the end and working your way back instead? It MIGHT take less time to do so based on the structure of that particular maze.

Thanks for the link. I've already solved my problem. The trick was that I tried to do what I had heard at the last lecture, not the simplest thing possible. But the simplest thing was what was necessary, while the thing they told us about was useless ;