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.
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.).
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
b is given by the formula
1 + |a - b|. If there are multiple solutions output all solutions.
Though I use
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.
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.