#include <stdio.h>
#define N 6
#define MAX 100
int main() {
  int i, j, k, t, max, min, index;
  static int table1[N][N] = {
    { 1, 1, 4, 3, 2, 2 },
    { 2, 2, 5, 6, 3, 3 },
    { 2, 3, 2, 2, 5, 4 },
    { 1, 1, 3, 5, 2, 2 },
    { 3, 2, 2, 3, 4, 3 },
    { 1, 4, 4, 3, 3, 2 }
  };
  static int table2[N][N];
  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
      table2[i][j] = MAX;
  
  for (i = 0; i < N; i++)
    table2[i][0] = table1[i][0];
  for (i = 0; i < N - 1; i++) {
    for (j = 0; j < N; j++) {
      for (k = j - 1; k <= j + 1; k++) {
        if (k < 0 || k >= N)
          continue;
        if ((t = table2[j][i] + table1[k][i + 1]) < table2[j][i + 1])
          table2[j][i + 1] = t;
      }
    }
  }      
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++)
      printf("%2d ", table2[i][j]);
    putchar('\n');
  }
  printf("path: ");
  max = 5;
  min = 0;
  for (i = 0; i < N; i++) {
    t = table2[min][i];
    index = min;
    for (j = min; j <= max; j++)
      if (table2[j][i] < t) {
        t = table2[j][i];
        index = j;
      }
    printf("%2d ", index);
    min = (index == 0) ? 0 : index - 1;
    max = (index == N - 1) ? N - 1 : index + 1;
  }
  return 0;
}
/* end */

 1  2  6  9 11 13 
 2  3  5  7  9 11 
 2  3  5  7  9 11 
 1  2  4  6  8 10 
 3  4  6  9 11 13 
 1  3  5  8 11 13 
path:  0  0  1  1  1  1