Taxis à San Francisco

Vous êtes chauffeur de taxi à San Francisco. Comme c'est le cas pour les chauffeurs de taxi, vous parcourez une grille où les seules directions valides que vous pouvez déplacer sont la gauche, la droite, le haut et le bas. Cependant, San Fransisco est très vallonné, donc la distance entre deux intersections adjacentes n'est pas nécessairement la même. Plus précisément, la distance entre une intersection en altitude aet une intersection adjacente en altitude bserait 1 + |a - b|. Votre objectif est de trouver tous les chemins les plus courts depuis votre origine en haut à gauche de la carte jusqu'à votre destination en bas à droite.

Contribution

Une grille bidimensionnelle d'altitudes entières dans le format le plus approprié (tableau bidimensionnel, tableau unidimensionnel avec largeur et / ou hauteur, etc.).

Production

Une séquence de directions à parcourir pour arriver dans le coin inférieur droit de l'entrée à partir du coin supérieur gauche dans la distance la plus courte possible étant donné la distance entre deux intersections adjacentes d'altitudes aet best donnée par la formule 1 + |a - b|. S'il existe plusieurs solutions, sortez toutes les solutions.

Bien que je l' utilise U, D, Let Rpour haut, en bas, à gauche, et à droite dans les exemples ci - dessous votre programme peut utiliser les quatre chaînes distinctes pour représenter les directions tant qu'il est compatible avec eux et à travers toutes les entrées.

Exemples

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

Il s'agit de code-golf, donc la réponse avec le nombre d'octets le plus court l'emporte.

JavaScript (ES6), 228 212 200 194 octets

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)

Contribution

Tableau aet largeur unidimensionnels wdans la syntaxe de curry(a)(w)

Production

Une liste de solutions séparées par des espaces telles que "DRDRRDR DRDRDRR"

Formaté et commenté

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
)                                      //

Cas de test

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));