7

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>

typedef struct {
    int x;
    int y;
} vec2;
const int n = 13;
const int m = 9;
int matrix[n][m] = {
    { 0,  5,  0, 11,  0, 12,  0,  5,  0},
    {11,  0,  3,  0,  5,  0,  3,  0,  6},
    { 0,  7,  0,  5,  0, 10,  0,  7,  0},
    {11,  0, 13,  0, 11,  0, 17,  0,  7},
    { 0, 10,  0,  5,  0,  9,  0,  9,  0},
    { 1,  0,  3,  0,  8,  0,  8,  0,  7},
    { 0,  5,  0,  6,  0,  4,  0, 14,  0},
    { 2,  0,  9,  0, 11,  0, 13,  0,  8},
    { 0,  7,  0,  4,  0,  8,  0,  6,  0},
    { 8,  0,  4,  0,  8,  0, 11,  0,  9},
    { 0,  8,  0, 11,  0, 13,  0, 10,  0},
    {12,  0,  9,  0, 17,  0, 10,  0,  6},
    { 0,  8,  0, 16,  0,  2,  0,  7,  0}
};

int min(int a, int b) {
    return ((a < b) ? a : b);
}

int main(void) {
    for (int i = 0; i < n; i += 2) {
        for (int j = 0; j < m; j += 2) {
            int mn = INT_MAX;
            if (i > 0) {
                mn = min(mn, matrix[i - 2][j] + matrix[i - 1][j]);
            }
            if (j > 0) {
                mn = min(mn, matrix[i][j - 2] + matrix[i][j - 1]);
            }
            if (mn != INT_MAX)
                matrix[i][j] = mn;
        }
    }
    vec2 way[(n + m) / 2];
    int brd = 0;
    int a = n - 1;
    int b = m - 1;
    while (a > 0 || b > 0) {
        way[brd++] = {a, b};
        int v = matrix[a][b];
        if (a > 0 && v == (matrix[a - 2][b] + matrix[a - 1][b])) {
            a -= 2;
        }
        else if (b != 0 && v == (matrix[a][b - 2] + matrix[a][b - 1])) {
            b -= 2;
        }
    }
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; ++ j) {
            printf("%2d ", matrix[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    printf("Min Way: %d\n", matrix[n - 1][m - 1]);
    way[brd++] = {0, 0};
    for (int i = brd - 1; i >= 0; -- i) {
        printf("(%d, %d)", way[i].x, way[i].y);
        if (i)
            printf(" -> ");
    }
    printf("\n");
    return 0;
}