#include <iomanip>
#include <iostream>
#include <map>
#include <vector>
#include <Windows.h>
using namespace std;

using double_vector_t = vector<vector<size_t>>;
using coordinate_t = pair<int, int>;


// заполняем мапу (дорога - посещали\нет)
void initRoads(map<coordinate_t, bool>& roads, const double_vector_t& matrix)
{
    for (size_t i = 0; i < matrix.size(); i++)
    {
        for (size_t j = 0; j < matrix[i].size(); j++)
        {
            if (matrix[i][j] != 0)
            {
                roads[coordinate_t(i, j)] = false;
            }
        }
    }
}

void initBlocked(map<size_t, map<size_t, size_t>>& blocked, const size_t& lineAmount)
{
    for (size_t i = 0; i < lineAmount; i++)
    {
        for (size_t j = 0; j < lineAmount; j++)
        {
            blocked[i][j] = 0;
        }
    }
}

bool isBlocked(map<size_t, map<size_t, size_t>>& blocked, const size_t& line, const size_t& id)
{
    return blocked[line][id] == 1;
}

void blockId(map<size_t, map<size_t, size_t>>& blocked, const size_t& line, const size_t& id)
{
    blocked[line][id] = 1;
}

void unblockId(map<size_t, map<size_t, size_t>>& blocked, const size_t& line, const size_t& id)
{
    blocked[line][id] = 0;
}

void markVisited(map<coordinate_t, bool>& roads, const coordinate_t& road)
{
    if (roads.find(road) != roads.end())
    {
        roads[road] = true;
    }
    if (roads.find(coordinate_t(road.second, road.first)) != roads.end())
    {
        roads[coordinate_t(road.second, road.first)] = true;
    }
}

void markUnvisited(map<coordinate_t, bool>& roads, const coordinate_t& road)
{
    if (roads.find(road) != roads.end())
    {
        roads[road] = false;
    }
    if (roads.find(coordinate_t(road.second, road.first)) != roads.end())
    {
        roads[coordinate_t(road.second, road.first)] = false;
    }
}

// Проверка на посещение всех
bool isRoadsVisited(const map<coordinate_t, bool>& roads)
{
    for (const auto& it : roads)
    {
        if (it.second != true)
        {
            return false;
        }
    }
    return true;
}

// Считает коллизиции для точки
size_t getCollisions(const double_vector_t& matrix, const size_t& line)
{
    size_t counter = 0;
    for (size_t j = 0; j < matrix[line].size(); j++)
    {
        if (matrix[line][j] != 0)
        {
            counter++;
        }
    }
    return counter;
}


void func(const double_vector_t& matrix,
          map<coordinate_t, bool>& roads,
          map<size_t, map<size_t, size_t>>& blocked,
          const size_t& line,
          size_t& currentLength,
          size_t*& bestLength,
          vector<size_t>& currentWay,
          vector<size_t>& bestWay)
{
    currentWay.push_back(line);
    if (isRoadsVisited(roads))
    {
        if (bestLength != nullptr)
        {
            if (*bestLength > currentLength)
            {
                bestWay = currentWay;
                bestLength = new size_t(currentLength);
            }
        }
        else
        {
            bestWay = currentWay;
            bestLength = new size_t(currentLength);
        }
    }
    else
    {
        for (size_t j = 0; j < matrix[line].size(); j++)
        {
            if (matrix[line][j] != 0 && !isBlocked(blocked, line, j))
            {
                markVisited(roads, coordinate_t(line, j));
                blockId(blocked, line, j);
                size_t moveCost = currentLength + matrix[line][j] + getCollisions(matrix, line);
                func(matrix, roads, blocked, j, moveCost, bestLength, currentWay, bestWay);

                markUnvisited(roads, coordinate_t(line, j));
                unblockId(blocked, line, j);
            }
        }
    }
    if (!currentWay.empty())
    {
        currentWay.pop_back();
    }
}

void printMatrix(const double_vector_t& matrix)
{
    cout << endl << "Matrix:" << endl;
    for (const auto& it : matrix)
    {
        for (const auto& jt : it)
        {
            cout << setw(3) << jt;
        }
        cout << endl;
    }
}

int main()
{
    map<coordinate_t, bool> roads;
    map<size_t, map<size_t, size_t>> blocked;
    // та не рабочая
    double_vector_t matrix__
    {
        {0, 10, 4, 8, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 8, 0, 6, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 4, 7, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 10, 7, 7, 0, 0, 13},
        {0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 8, 0, 0, 0, 0, 4, 0, 5},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 7, 0, 0, 0, 6, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5},
        {0, 0, 0, 0, 0, 11, 0, 0, 12, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    };

    double_vector_t matrix{
        {0, 10, 4, 8, 0},
        {10, 0, 8, 0, 6},
        {4, 8, 0, 4, 7},
        {8, 0, 4, 0, 8},
        {0, 6, 7, 8, 0}

    };
    size_t currentLength = 0;
    size_t* bestLength = nullptr;
    //para - (line, blocked j's)
    vector<size_t> currentWay;
    vector<size_t> bestWay;
    printMatrix(matrix);

    initRoads(roads, matrix);
    initBlocked(blocked, matrix.size());

    for (size_t i = 0; i < matrix.size(); i++)
    {
        func(matrix, roads, blocked, 0, currentLength, bestLength, currentWay, bestWay);
    }
    cout << "Best length: " << (bestLength != nullptr ? *bestLength : 0) << endl;
    for (size_t i = 0; i < bestWay.size(); i++)
    {
        cout << bestWay[i] + 1 << (i + 1 != bestWay.size() ? " -> " : ".");
    }
    return 0;
}