Trip Mapper

Problem Statement

Many trip planning programs exist, and are set up to give you the shortest driving distance between two locations. However, frequently the directions involve taking several quick turns on small side roads, and this can be very confusing. Often times, someone who knows the area well will be able to suggest another route that, although perhaps slightly longer, involves a much simpler set of directions. For the purposes of this problem, we define the simplest set of directions as being the set of directions involving the fewest turns.

In a certain city, all of the roads have all corners and end points defined at a lattice point (one with integer coordinates), and all roads travel exactly east-west or north-south.

You are given Strings start and end representing the coordinates of the starting point and ending point of the trip. You are also given a String[], roads, which defines all of the roads in a city. Each element of roads is formatted as "x1 y1 x2 y2" indicating a road from (x1,y1) to (x2,y2). You may assume that there is an intersection wherever two roads cross each other. (E.g. you can always turn from one road to the other at such a point, there are no bridges or tunnels).

The directions from the start to end point should start with the direction of travel, 'N', 'S', 'E', or 'W', and number of block to travel. Turns should be indicated by the letter 'R' or 'L' (right or left) and the number of blocks to travel. Thus, "N3R4" would mean go north three blocks, turn right and go four more blocks. "N2R2R2R2" would lead you right back to the starting point.

You are to return a String representing the simplest set of directions (the one with the fewest turns) from the start point to the end point. If there is a tie, return the one that comes first alphanumerically (for example, "N10R5L4" is preferred over "N7R5L7" since they both involve 2 turns, but the former comes first alphanumerically). If it is impossible to get from the origin to the destination on the roads as described, you should return an empty string ("").

Definition

Notes

• North is the +y direction, while east is the +x direction.
• When comparing strings alphanumerically, order them by the ASCII value of the first character for which the two strings differ (numbers come before letters).
• Your return should not have any extra leading zeros in the numbers.

Constraints

• Each number in the inputs will an integer between 0 and 500, inclusive, and will not contain any extra leading zeros.
• start and end will be formatted as two numbers separated by a single space.
• start and end will not be the same.
• roads will contain between 1 and 50 elements, inclusive.
• Each element of roads will be formatted as 4 numbers separated by single spaces.
• Each road will be directly north-south or east-west.
• No two roads will overlap (though they may touch at a single point).
• Each road will have length of at least one (the roads will not be points).

Examples

0)


"10 10"
"20 10"
{"10 10 10 19", "10 19 20 19", "20 19 20 10", "10 10 11 10",
 "11 10 11 9", "11 9 19 9", "19 9 19 10", "19 10 20 10"}
Returns: "N9R10R9"

Here, there are two different ways to get from the start point to the end point. Although the northern route is much longer (28 units), it requires only two turns. The shorter, southern route takes four turns. We start out going north 9 units, turn right, go 10 units, and then turn right again, and go 9 units to reach our destination. The directions for the "easiest" route are thus "N9R10R9".

1)


"1 0"
"9 0"
{"0 0 10 0"}
Returns: "E8"

2)


"0 0"
"30 30"
{"0 0 0 10","0 10 10 10","10 10 10 20","10 20 20 20","20 20 20 30","20 30 30 30",
 "0 0 9 0","9 0 9 9","9 9 18 9","18 9 18 18","18 18 27 18","27 18 27 30"
 }
Returns: "N10R10L10R10L10R10"

3)


"0 0"
"10 10"
{"0 0 10 0","10 1 10 10"}
Returns: ""

4)


"1 10"
"9 10"
{"0 10 5 10", "5 10 10 10"}
Returns: "E8"
Notice here that we have two roads which join together, and are, effectively, a single road.
5)


"0 0"
"500 500"
{"0 0 0 500","20 0 20 500","41 0 41 500","62 0 62 500","83 0 83 500",
 "104 0 104 500","125 0 125 500","145 0 145 500","166 0 166 500",
 "187 0 187 500","208 0 208 500","229 0 229 500","250 0 250 500",
 "270 0 270 500","291 0 291 500","312 0 312 500","333 0 333 500",
 "354 0 354 500","375 0 375 500","395 0 395 500","416 0 416 500",
 "437 0 437 500","458 0 458 500","479 0 479 500","500 0 500 500",
 "0 0 500 0","0 20 500 20","0 41 500 41","0 62 500 62","0 83 500 83",
 "0 104 500 104","0 125 500 125","0 145 500 145","0 166 500 166",
 "0 187 500 187","0 208 500 208","0 229 500 229","0 250 500 250",
 "0 270 500 270","0 291 500 291","0 312 500 312","0 333 500 333",
 "0 354 500 354","0 375 500 375","0 395 500 395","0 416 500 416",
 "0 437 500 437","0 458 500 458","0 479 500 479","0 500 500 500"}
Returns: "E500L500"

6)


"400 400"
"405 414"
{"400 400 400 410",
 "400 410 405 410",
 "405 410 405 414",
 "400 407 405 407",
 "405 407 405 410"}
Returns: "N10R5L4"
"N10R5L4" and "N7R5L7" are both valid sets of directions with two turns, but the former comes first alphanumerically.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.