fork download
copy 
  1.  
  2. var checkerBoard = [undefined, [undefined, null, null, 5, null, null], [undefined, null, 6, 7, 0, null], [undefined, 3, 5, 7, 8, 2], [undefined, 7, 6, 1, 1, 4], [undefined, 6, 7, 4, 7, 8]];
  3. var n = 5;
  4.  
  5. var q = [undefined, [],[],[],[],[]];
  6. var p = [undefined, [],[],[],[],[]];
  7.  
  8.  
  9.  
  10. function c(i, j) {
  11.     return checkerBoard[i][j];
  12. }
  13.  
  14. function minCost(i, j) {
  15.     if (j < 1 || j > n) { return Infinity; }
  16.     else if (i === 1) { return c(i, j); }
  17.     else { return Math.min(minCost(i - 1, j - 1), Math.min(minCost(i - 1, j), minCost(i - 1, j + 1))) + c(i, j); }
  18.  }
  19.  
  20. function computeShortestPathArrays() {
  21.  
  22.     for (var x = 1; x <= n; x++){
  23.         q[1][x] = c(1, x);
  24.     }
  25.     for (var y = 1; y <= n; y++){
  26.         q[y][0] = Infinity;
  27.         q[y][n + 1] = Infinity;
  28.     }
  29.     for (var y = 2; y <= n; y++){
  30.         for (var x = 1; x <= n; x++){
  31.             var m = Math.min(q[y - 1][ x - 1], Math.min(q[y - 1][x], q[y - 1][x + 1]));
  32.             q[y][x] = m + c(y, x);
  33.  
  34.             if (m === q[y - 1][x - 1]) {
  35.                 p[y][x] = -1;
  36.             }
  37.             else if (m === q[y - 1][x]) {
  38.                 p[y][x] = 0;
  39.             }
  40.             else {
  41.                 p[y][x] = 1;
  42.             }
  43.         }
  44.     }
  45. }
  46.  
  47. function computeShortestPath() { 
  48.  
  49.     computeShortestPathArrays();
  50.     var minIndex = 1;
  51.     var min = q[n][1];
  52.     for (var i = 2; i <= n; i++){
  53.         if (q[n][i] < min) {
  54.             minIndex = i;
  55.             min = q[n][i];
  56.         }        
  57.     }
  58.     printPath(n, minIndex);
  59. }
  60.  
  61. function printPath(y, x) { 
  62.     process.stdout.write("" + x);
  63.  
  64.     process.stdout.write("<-");
  65.     if (y === 2) {
  66.  
  67.         process.stdout.write("" + ((x) + p[y][x]));
  68.         console.log("");
  69.     }
  70.     else { printPath(y - 1, x + p[y][x]) }
  71.  
  72. }
  73.  
  74. computeShortestPath();
  75.  
  76. console.log("");
  77.  
  78. console.log(/*"\narray p == " +*/ p);
  79.  
  80. console.log(/*"array q == " +*/ q);
  81.  
  82. console.log(/*"array checkerBoard == " +*/ checkerBoard);
Success #stdin #stdout 0.04s 277888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3<-4<-5<-4<-5

[ undefined,
  [],
  [ , 1, 1, 1, 1, 1 ],
  [ , 0, -1, 1, 0, -1 ],
  [ , 0, -1, -1, 1, 0 ],
  [ , 1, 1, 1, 0, -1 ] ]
[ undefined,
  [ Infinity, null, null, 5, null, null, Infinity ],
  [ Infinity, 0, 6, 7, 0, 0, Infinity ],
  [ Infinity, 3, 5, 7, 8, 2, Infinity ],
  [ Infinity, 10, 9, 6, 3, 6, Infinity ],
  [ Infinity, 15, 13, 7, 10, 11, Infinity ] ]
[ undefined,
  [ undefined, null, null, 5, null, null ],
  [ undefined, null, 6, 7, 0, null ],
  [ undefined, 3, 5, 7, 8, 2 ],
  [ undefined, 7, 6, 1, 1, 4 ],
  [ undefined, 6, 7, 4, 7, 8 ] ]
https://ideone.com/dGjmSw
language:
Node.js (node 20.14)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!