Taxicab in San Francisco

Question

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.

Answer 1

JavaScript (ES6), 228 212 200 194 bytes

a=>w=>(B=1/0,(F=(r,p,s,b=a[p])=>p-a.length+1?1/b&&([...a[p]='RDUL'].map((c,d)=>d|p%w<w-1&&d-3|p%w&&F(r+c,P=p+[1,w,-w,-1][d],s+1+Math.abs(b-a[P]))),a[p]=b):R=s>B?R:s<B?(B=s,r):R+' '+r)('',0,0),R)

Input

One-dimensional array a and width w in currying syntax (a)(w)

Output

A space-separated list of solutions such as "DRDRRDR DRDRDRR"

Formatted and commented

a => w => (                            // given an array 'a' and a width 'w'
  B = 1 / 0,                           // B = best score so far, initialized as +Infinity
  (                                    //
    F = (                              // F = recursive function with:
      r,                               //   - r = current path (string)
      p,                               //   - p = current position in grid
      s,                               //   - s = current score
      b = a[p]                         //   - b = backup of current cell
    ) =>                               //
    p - a.length + 1 ?                 // if we haven't reached our destination:
      1 / b && (                       //   if the current cell is valid:
        [...a[p] = 'RDUL']             //     invalidate the current cell
        .map((c, d) =>                 //     for each possible direction:
          d | p % w < w - 1 &&         //       check right boundary
          d - 3 | p % w &&             //       check left boundary
          F(                           //       do a recursive call with:
            r + c,                     //         - new direction appended to the path
            P = p + [1, w, -w, -1][d], //         - updated position
            s + 1 + Math.abs(b - a[P]) //         - updated score
          )                            //
        ),                             //
        a[p] = b                       //     restore current cell value
      )                                //
    :                                  // else:
      R = s > B ?                      //   if the current score is worse than B:
        R                              //     keep the previous solution
      : s < B ?                        //   if the current score is better than B:
        (B = s, r)                     //     update best score / store path as new solution
      : R + ' ' + r                    //   if it's just as good: append path to solution
  )('', 0, 0),                         // initial call to F with r = '', p = 0, s = 0
  R                                    // return solution
)                                      //

Test cases

let f =

a=>w=>(B=1/0,(F=(r,p,s,b=a[p])=>p-a.length+1?1/b&&([...a[p]='RDUL'].map((c,d)=>d|p%w<w-1&&d-3|p%w&&F(r+c,P=p+[1,w,-w,-1][d],s+1+Math.abs(b-a[P]))),a[p]=b):R=s>B?R:s<B?(B=s,r):R+' '+r)('',0,0),R)

console.log(f([
  0, 3, 0, 0, 0,
  0, 2, 0, 2, 0,
  0, 0, 0, 3, 0
])(5));

console.log(f([
  3
])(1));

console.log(f([
  11, 11, 11,
  11, 11, 11,
  11, 11, 11
])(3));

console.log(f([
  7, 8, 1, -1, 0,
  4, 4, 6, -1, 7,
  3, 4, 4,  2, 8,
  2, 5, 2, -1, 2
])(5));

Answer 2

Python3, 383 bytes

E=enumerate
def f(b):
 d,D={(x,y):v for x,r in E(b)for y,v in E(r)},{}
 q=[(0,0,0,'',[(0,0)])]
 for x,y,c,m,p in q:
  if(x,y)==(len(b)-1,len(b[0])-1):D[c]=D.get(c,[])+[m];continue
  for U,X,Y in[('R',0,1),('L',0,-1),('U',-1,0),('D',1,0)]:
   if(n:=(x+X,y+Y))not in d:continue
   C=1+abs(d[(x,y)]-d[n])
   if n not in p and(D=={}or C<=min(D)):q+=[(*n,c+C,m+U,p+[n])]
 return D[min(D)]

Try it online!