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