Help:Graph contest problem: maybe a modified Dijkstra or another alternative algorithm

Question

Hi you all,

I'm trying to do this contest exercise about graphs:

XPTO is an intrepid adventurer (a little too temerarious for his own good) who boasts about exploring every corner of the universe, no matter how inhospitable. In fact, he doesn't visit the planets where people can easily live in, he prefers those where only a madman would go with a very good reason (several millions of credits for instance). His latest exploit is trying to survive in Proxima III. The problem is that Proxima III suffers from storms of highly corrosive acids that destroy everything, including spacesuits that were especially designed to withstand corrosion.

Our intrepid explorer was caught in a rectangular area in the middle of one of these storms. Fortunately, he has an instrument that is capable of measuring the exact concentration of acid on each sector and how much damage it does to his spacesuit. Now, he only needs to find out if he can escape the storm. Problem

The problem consists of finding an escape route that will allow XPTO to escape the noxious storm. You are given the initial energy of the spacesuit, the size of the rectangular area and the damage that the spacesuit will suffer while standing in each sector.

Your task is to find the exit sector, the number of steps necessary to reach it and the amount of energy his suit will have when he leaves the rectangular area. The escape route chosen should be the safest one (i.e., the one where his spacesuit will be the least damaged). Notice that XPTO will perish if the energy of his suit reaches zero.

In case there are more than one possible solutions, choose 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.

Constraints 0 < E ≤ 30000 the suit's starting energy
0 ≤ W ≤ 500 the rectangle's width
0 ≤ H ≤ 500 rectangle's height
0 < X < W the starting X position
0 < Y < H the starting Y position
0 ≤ D ≤ 10000 the damage sustained in each sector

Input

The first number given is the number of test cases. Each case will consist of a line with the integers E, X and Y. The following line will have the integers W and H. The following lines will hold the matrix containing the damage D the spacesuit will suffer whilst in the corresponding sector. Notice that, as is often the case for computer geeks, (1,1) corresponds to the upper left corner.

Output

If there is a solution, the output will be the remaining energy, the exit sector's X and Y coordinates and the number of steps of the route that will lead Rodericus to safety. In case there is no solution, the phrase Goodbye cruel world! will be written.

Sample Input

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 

Sample Output

12 5 1 8  
Goodbye cruel world!  
5 1 4 2

Basically, I think we have to do a modified Dijkstra, in which the distance between nodes is the suit's energy (and we have to subtract it instead of suming up like is normal with distances) and the steps are the ....steps made along the path. The pos with the bester binomial (Energy,num_Steps) is our "way out".

Important : XPTO obviously can't move in diagonals, so we have to cut out this cases.

I have many ideas, but I have such a problem implementing them...

Could someone please help me thinking about this with some code or, at least, ideas?

Am I totally wrong?

Answer 1

You don't have to treat this with any unconventional conversions like you said (subtracting instead of adding, etc).

The shortest path from one node to another is one that minimizes the total damage to the suit along the way, regardless of whether or not this journey will kill you.

Just find the shortest path from START to EXIT, summing up edge weights as is usual Dijkstra approach, and then consider if this shortest path is feasible for the given suit power. If it isn't, then Goodbye cruel world!.

If you insist on pruning the search once you know that you can definitely not reach the EXIT, then adding it after the above implementation is trivial: as you're expanding your search horizon in your Dijkstra search, if even going to the next closest node to expand from kills you, then the rest of search space also will, so you can just abort and Goodbye cruel world!.

As for the graph itself, conceptually this is what you want. The vertices of the directed graph consists of all nodes in the grid, plus an artificial EXIT node.

• All edge nodes have a directed edge to EXIT; the weight of these edges is 0
• All neighboring (non-diagonal) node have directed edges between them
  • From node n1 to n2, the weight of the edge (i.e. the cost damage of travelling from n1 to n2) is the damage incurred by staying at node n2 (let's call this damageAt[n2], which you get from D matrix in input).

So minimum total amount of damage that one must sustain to go from START to EXIT is damageAt[START] + costOf(shortestPathBetween(START, EXIT)).

In summary, this approach:

• Only requires standard Dijkstra implementation
• Requires only very small modification to add pruning
• Requires only very simple transformation from the input grid to the directed graph

Answer 2

Since this is a contest problem, I'll just give a small hint:

In this example, it's the nodes that have weight, not the edges. One way of converting such a graph to the usual kind is to replace each node with two nodes, an in node and an out node, and a directed edge from in to out with weight equal to the original node's weight. Then for each directed edge in the original graph, put a directed edge from the out node of one to the in node of the next.

Your idea sounds good - go with it.

By the way, when working these problems, try to work out the implementation for yourself. It rarely helps to simply see someone else's implementation. Ask for help on the algorithm if you need to, but implement it yourself.