Problem Statement |
| | You need to get home from work in an hour, but your car's steering is practically useless. So, you've decided that you want to take the route with the fewest turns possible. You've modeled the relevant streets as straight lines in a plane, each of which is parallel to the x or y axis, and now all that's left to do is figure out the best path.
You will be given a String[], roads, each element of which represents a single road in the format "X1 Y1 X2 Y2", where (X1,Y1) and (X2,Y2) are the two end points of the road. You may assume that any two roads that cross paths have an intersection where you can switch from one road to the other. You will also be given two Strings, start and end, representing the starting and ending points of your trip in the form "X Y". Both start and end will be along roads, and you may start facing in any direction you like. You are to return an int representing the minimum number of turns required to get home (the constraints ensure that there will be at least one path home). |
| |
Definition |
| | | Class: | FewestTurns | | Method: | numTurns | | Parameters: | String[], String, String | | Returns: | int | | Method signature: | int numTurns(String[] roads, String start, String end) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | roads will contain between 1 and 50 elements, inclusive. |
| - | Each element of roads will be formatted as "X1 Y1 X2 Y2". |
| - | X1, Y1, X2, and Y2 will each be between 0 and 100, inclusive. |
| - | X1 will be less than or equal to X2. |
| - | Y1 will be less than or equal to Y2. |
| - | Either X1 will equal X2 or Y1 will equal Y2, but not both. |
| - | start and end will each be formatted as "X Y", where X,Y will be on some road. |
| - | None of the inputs will have extra leading zeros, or extra spaces. |
| - | No two roads will overlap (though they may cross). |
| - | It will be possible to get from start to end. |
| |
Examples |
| 0) | |
| | {"0 0 10 0","10 0 10 10","10 10 20 10"} | "0 0" | "20 10" |
| Returns: 2 | | We can start by driving from (0,0) to (10,0). From there, we can turn left, and go to (10,10). A right turn and a little more driving will bring us to (20,10). |
|
|
| 1) | |
| | {"0 0 40 0","30 0 30 10","0 10 50 10",
"5 0 5 5","5 5 10 5","10 5 10 10"} | "1 0" | "19 10" |
| Returns: 2 | | We can go from (1,0) to (30,0). Then, we turn left and go to (30,10), followed by another left turn, and a drive to (19,10). Note that this is not the shortest path. |
|
|
| 2) | |
| | {"0 0 1 0",
"1 0 2 0",
"2 0 3 0",
"3 0 4 0",
"4 0 5 0"} | "0 0" | "5 0" |
| Returns: 0 | |
|
| 3) | |
| | {"0 0 0 100","1 0 1 100","2 0 2 100","3 0 3 100","4 0 4 100","5 0 5 100",
"6 0 6 100","7 0 7 100","8 0 8 100","9 0 9 100","10 0 10 100","11 0 11 100",
"12 0 12 100","100 0 100 100","99 0 99 100","98 0 98 100","97 0 97 100",
"96 0 96 100","95 0 95 100","94 0 94 100","93 0 93 100","92 0 92 100",
"91 0 91 100","90 0 90 100","89 0 89 100","0 0 100 0","0 1 100 1",
"0 2 100 2","0 3 100 3","0 4 100 4","0 5 100 5","0 6 100 6","0 7 100 7",
"0 8 100 8","0 9 100 9","0 10 100 10","0 11 100 11","0 12 100 12",
"0 100 100 100","0 99 100 99","0 98 100 98","0 97 100 97","0 96 100 96",
"0 95 100 95","0 94 100 94","0 93 100 93","0 92 100 92","0 91 100 91",
"0 90 100 90","0 89 100 89"} | "0 0" | "100 100" |
| Returns: 1 | |
|
| 4) | |
| | {"9 93 43 93","9 53 9 93","9 53 96 53","96 53 96 71","17 71 96 71","17 18 17 71",
"17 18 99 18","99 18 99 86","93 86 99 86","93 1 93 86","32 1 93 1","32 1 32 18",
"32 18 32 49","32 49 68 49","68 40 68 49","54 40 68 40","54 40 54 54","54 54 54 90",
"15 90 54 90","2 90 15 90","2 44 2 90","2 1 2 44","2 1 24 1","24 1 24 47","24 47 69 47",
"69 47 69 68","28 68 69 68","28 68 28 98","16 98 28 98","16 84 16 98","16 84 38 84",
"38 67 38 84","2 67 38 67","0 67 2 67","0 54 0 67","0 54 29 54","29 54 86 54",
"86 52 86 54","86 27 86 52","86 13 86 27","52 13 86 13","52 13 52 97","52 97 70 97",
"70 97 90 97","90 84 90 97","90 29 90 84","21 29 90 29","21 4 21 29","21 2 21 4","21 2 41 2"} | "43 93" | "41 2" |
| Returns: 6 | |
|