4 replies to this topic

[chili5]

On our first contest we had this problem here that dealt with finding the optimal distance from one letter to another. I have absolutely no idea how to do this, but these problems keep coming up, and I was curious as what things I should look into, to better understand this. I'm not going to get very far if I don't learn how to go about these.

Thanks for the help.

chili :)

[Xav]

You'll have to employ some logic. Try the routes, and find the best one.

[WingedPanther]

My approach:
Store the map in an array with an array of int of the same size.
Start out the int array with values of -1.
Seed the initial location with 0.
Then update all reachable locations that are adjacent to 0 with 1's.
Then update all reachable locations that are adjacent to 1's and are -1 to 2.
Repeat until you reach your next waypoint.
Reset all values except your current waypoint to -1.
repeat. the above process to reach your next waypoint.

The idea is that if you mark all locations based on their distance from a given point, you have rings of distances spreading out. Exploit that.

[chili5]

Thank you Winged.

That's very helpful.

[Aereshaa]

I would do it this way:
1. build a table of distances between marked points, based on a simple recursive algorithm.
2. perform addition.

the algorithm to find the optimum distance between two points. the function takes the distance so far n, and two points, as well as an array of the previous points
1. if point is a wall, return infinity. (biggr than all others: will never be the minimum except when there is no route.)
2. if at destination, return n.
3. if current point is in list of previous points return infinity.
4. find optimum distance from points above below, left and right, passing n+1.
return minimum of those.

what do you think?