14
2
You are a taxicab driver in San Francisco. As is typical of taxicab drivers, you are navigating a grid where the only valid directions you can move are the left, right, up, and down. However, San Fransisco is very hilly so the distance between two adjacent intersections is not necessarily the same. More specifically, the distance between an intersection at altitude a
and an adjacent intersection at altitude b
would be 1 + |a - b|
. Your goal is to find all the shortest paths from your origin at the top left of the map to your destination at the bottom right.
Input
A two-dimensional grid of integer altitudes in whichever format is most convenient (two-dimensional array, one-dimensional array with width and/or height, etc.).
Output
A sequence of directions to travel to arrive at the bottom right corner of the input from the top left in the shortest distance possible given the distance between two adjacent intersections of altitudes a
and b
is given by the formula 1 + |a - b|
. If there are multiple solutions output all solutions.
Though I use U
, D
, L
, and R
for up, down, left, and right in the examples below your program may use any four distinct strings to represent the directions so long as it is consistent with them in and across all inputs.
Examples
Input:
0 3 0 0 0
0 2 0 2 0
0 0 0 3 0
Output:
D D R R U U R R D D
Input:
3
Output:
<empty>
Input:
11 11 11
11 11 11
11 11 11
Output:
R R D D
R D R D
R D D R
D R R D
D R D R
D D R R
Input:
7 8 1 -1 0
4 4 6 -1 7
3 4 4 2 8
2 5 2 -1 2
Output:
D R D R R D R
D R D R D R R
This is code-golf so the answer with the shortest byte count wins.
1Are the altitudes always less than 10 ? (they are on the examples, but will they always be?) – Dada – 2016-11-11T22:00:34.640
@Dada the altitudes are not necessarily less than 10 (they can also be negative), I have updated the examples accordingly. – 0 ' – 2016-11-11T23:00:13.437
when i saw that this post was active i was suuuuuuper excited - i thought someone had posted an answer in taxi ! maybe one day – space junk – 2017-08-18T16:01:28.893