pathfinding in 2d array

Question

I am currently working on a project, in which I have to perform tasks with a 2 dimensional array, containing random numbers. The array forms a grid, which represents peaks (heights) of a mountain. I resolved every task except the last one:

The last task would be to find if there exists a path, which goes form the smallest peak to the highest (it doesn't have to be the shortest). The path should consist of ever growing peaks, I can't step on a lower peak.

Here's an example, for simplicity's sake, represented on 3x3 grid (original is much bigger, and not necessary square-like, it's generated as the user wants and numbers are completely random).

2  4  5    
1  3  8
9  7  10

The possible ways would be 1-3-7-10, 1-3-8-10, 1-2-4-5-8-10.

I am pretty sure, that I should use some kind of a recursion. I read about a* pathfinder, but to work with it, I have to have a "map" with the "obstacles" (the nodes where I cannot step = smaller peaks) and that is exactly, which I can't make, as you only find it out on the go.

By that I mean I could put number 7 on a "exception list" -as steps 1-9-7 are forbidden, but steps 1-3-7-10 are perfect, so putting 7 on a exception list would be a mistake.

Answer 1

The key is to first convert your array into a "digraph" which is a directed-graph consisting only of the valid cell-to-cell moves according to your rules. This digraph would be an array or list of entries consisting of: {FromCell, ToCell}

Your digraph would contain data like this:

2,4
4,5
5,8
1,2
1,3
1,9
3,4
3,8
3,7
8,10
7,10

From here you should be able to apply the A* algorithm, or any of a number of others.

(note: I am not posting a completed answer, as I assume that you want to do this yourself)

---

That said, you could just do a brute-force recursive search with back-tracking. This is the simplest solution, though probably not the most efficient.