7

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

typedef struct {
    int x;
    int y;
} vec2;
const int n = 17;
const int m = 11;
int matrix[n][m] = {
    {0, 9, 0, 14, 0, 13, 0, 8, 0, 6, 0},
    {8, 0, 3, 0, 5, 0, 8, 0, 3, 0, 7},
    {0, 4, 0, 5, 0, 10, 0, 8, 0, 9, 0},
    {6, 0, 12, 0, 11, 0, 11, 0, 11, 0, 7},
    {0, 13, 0, 5, 0, 4, 0, 12, 0, 13, 0},
    {5, 0, 6, 0, 5, 0, 9, 0, 7, 0, 5},
    {0, 6, 0, 11, 0, 10, 0, 5, 0, 8, 0},
    {10, 0, 14, 0, 13, 0, 15, 0, 14, 0, 9},
    {0, 10, 0, 5, 0, 9, 0, 4, 0, 9, 0},
    {7, 0, 12, 0, 7, 0, 12, 0, 8, 0, 7},
    {0, 2, 0, 7, 0, 7, 0, 7, 0, 14, 0},
    {8, 0, 8, 0, 15, 0, 6, 0, 11, 0, 8},
    {0, 9, 0, 9, 0, 8, 0, 9, 0, 7, 0},
    {9, 0, 11, 0, 7, 0, 8, 0, 14, 0, 2},
    {0, 6, 0, 12, 0, 10, 0, 5, 0, 11, 0},
    {14, 0, 9, 0, 10, 0, 9, 0, 10, 0, 5},
    {0, 3, 0, 13, 0, 6, 0, 5, 0, 5, 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;
}