Найти оптимальный путь путешественника прохождение которого дает максимальную сумму призов

#include <iostream>
#include <vector>
#include <algorithm>
 
void f(std::vector<std::vector<int>> v, std::vector<std::vector<std::vector<int>>> &paths)
{
    int i = v.back()[0];
    int j = v.back()[1];
    // Move ↑
    if (i > 0)
    {
        if (i == 1 && j == 7)
        {
            std::vector<std::vector<int>> t(v);
            t.push_back({0, 7});
            paths.push_back(t);
        }
        else
        {
            std::vector<std::vector<int>> t(v);
            t.push_back({i-1, j});
            f(t, paths);
        }
    }
    // Move →
    if (j < 7)
    {
        if (i == 0 && j == 6)
        {
            std::vector<std::vector<int>> t(v);
            t.push_back({0, 7});
            paths.push_back(t);
        }
        else
        {
            std::vector<std::vector<int>> t(v);
            t.push_back({i, j+1});
            f(t, paths);
        }
    }
    // Move ↖ or ↗
    if (i > 0)
    {
        // Move ↖
        if (j > 0)
        {
            std::vector<std::vector<int>> t(v);
            t.push_back({i-1, j-1});
            f(t, paths);
        }
        // Move ↗
        if (j < 7)
        {
            if (i == 1 && j == 6)
            {
                std::vector<std::vector<int>> t(v);
                t.push_back({0, 7});
                paths.push_back(t);
            }
            else
            {
                std::vector<std::vector<int>> t(v);
                t.push_back({i-1, j+1});
                f(t, paths);
            }
        }
    }
}
 
int main()
{
    const int A[8][8]
    {
        {5, -1, 2, 4, -2, -3, 4, 4},
        {-1, 2, -2, -1, 5, 2, -3, 2},
        {2, -1, 3, 5, -1, 2, -1, 3},
        {1, -2, 1, 3, 3, -4, -4, 7},
        {-2, 4, -2, 3, -5, 1, -3, -4},
        {-3, -2, -1, -5, 2, 1, -3, -2},
        {-2, -3, -2, 4, -2, 3, -1, -5},
        {1, -2, -2, -3, -2, -1, 4, 3}
    };
    std::vector<std::vector<std::vector<int>>> paths;
    f({{7, 0}}, paths);
    int n = paths.size();
    std::cout << "Number of all possible paths: " << n << '\n';
    auto sum = [&A](std::vector<std::vector<int>> v)
    {
        int s = 0;
        for (const auto &i : v)
            s += A[i[0]][i[1]];
        return s;
    };
    std::vector<int> s;
    s.reserve(n);
    for (const auto &p : paths)
        s.push_back(sum(p));
    auto it = std::max_element(s.begin(), s.end());
    std::cout << "Max sum: " << *it << '\n';
    std::vector<std::vector<int>> path = paths[std::distance(s.begin(), it)];
    for (const auto &i : path)
        std::cout << "[" << i[0] << ", " << i[1] << "]\n";
}

Number of all possible paths: 6949276
Max sum: 35
[7, 0]
[7, 1]
[7, 2]
[6, 3]
[6, 4]
[6, 5]
[5, 4]
[4, 3]
[3, 2]
[3, 3]
[3, 4]
[2, 3]
[2, 4]
[2, 5]
[1, 4]
[1, 5]
[0, 6]
[0, 7]