Can anyone give me tips how to solve this using Graphs in C or Java?

Can anyone give me tips how to solve this using Graphs in C or Java?

I have a rectangular sector, that I have to escape, and I have energy that goes disappear every step that i give in the area. I have to give the only one possible solution, the one that uses the least number of steps. If there are at least two sectors with the same number of steps (X1, Y1) and (X2, Y2) then choose the first if X1 < X2 or if X1 = X2 and Y1 < Y2. the position( 1,1) corresponds to the upper left corner.

Examples:

This is one sector,and i start with 40 of energy and in the position (3,3)

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

the best solution to exit the sector is the position (5, 1) the remain energy is 12 and i need 8 steeps to leave the area.

for this sector i start with 8 of energy and in the position (3,4).

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

And for this one there is no way out, cause it looses all the energy.

You can create graph with each edge having a corresponding price (energy that will disappear if you move by it). Like:

4 3 3
2 5 2
2 1 2

will produce a graph lower part of this graph looks like:

       *
       |
       |5        
    2  |  2
  *----*----*
       |
       |1
       *

Then you can apply Dijkstra's algorithm to find the cheapest path on this graph.

Also pay attention to the JGraphT library in Java.