Giải bài CharlietheDog bằng sinh hoán vị

CharlietheDog.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

#define MAX 1000 // cost will never reach this value

struct POSITION
{
    int row;
    int col;

    POSITION()
    {
        this->setPosition(-1, -1);
    }

    POSITION(int row, int col)
    {
        this->setPosition(row, col);
    }

    void setPosition(int row, int col)
    {
        this->row = row;
        this->col = col;
    }

    int calculateDistance(const POSITION &other) const
    {
        return std::abs(this->row - other.row) + abs(this->col - other.col);
    }
};

// Chuyển vị trí chó, nhà, đồ ăn về dạng danh sách, thay vì để trong matrix. Phần tử đầu là con chó, phần tử cuối là
// cái nhà, các phần tử giữa là đô ăn
vector<POSITION> matrixToList(const vector<string> &strArr)
{
    vector<POSITION> positionList;
    POSITION dog, home;
    positionList.push_back(dog);

    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            if (strArr[i][j] == 'F')
            {
                positionList.push_back(POSITION(i, j));
            }
            else if (strArr[i][j] == 'C')
            {
                dog.setPosition(i, j);
            }
            else if (strArr[i][j] == 'H')
            {
                home.setPosition(i, j);
            }
        }
    }

    positionList[0] = dog; // update dog position
    positionList.push_back(home);
    return positionList;
}

// Ma trận chi phí là ma trận mà mỗi phần tử C[i][j] lưu chi phí đi từ POSITION i tới POSITION j
vector<vector<int>> initCostMatrix(const vector<POSITION> &positionList)
{
    vector<vector<int>> costs;
    for (const auto &item : positionList)
    {
        vector<int> line(positionList.size(), 0);
        costs.push_back(line);
    }

    for (int i = 0; i < positionList.size(); ++i)
    {
        costs[i][i] = 0;

        for (int j = i + 1; j < positionList.size(); ++j)
        {
            costs[i][j] = costs[j][i] = positionList[i].calculateDistance(positionList[j]);
        }
    }

    // Khúc này in matrix chi phí ra coi cho dzui thôi
    // for (int i = 0; i < costs.size(); ++i)
    // {
    //     for (int j = 0; j < costs[i].size(); ++j)
    //     {
    //         cout << costs[i][j] << "\t";
    //     }

    //     cout << endl;
    // }

    return costs;
}

// Hàm tính chi phí một hành trình
int calculateRouteCost(const vector<vector<int>> &costs, const vector<int> &route)
{
    int sum = 0;

    for (int i = 1; i < route.size(); ++i)
    {
        int from = route[i - 1];
        int to = route[i];
        sum += costs[from][to];
    }

    return sum;
}

// Giải thuật sinh hoán vị Heap lụm trên wikipedia (https://en.wikipedia.org/wiki/Heap%27s_algorithm)
//      k: số phần tử của mảng
//      array: mảng
//      những tham số khác: thêm vô để tính chi phí cho mỗi cách con chó đi (mỗi hoán vị là 1 cách con chó đi)
void genPermutation(int k, int *array, const vector<vector<int>> &costs, vector<int> &route, int &minRet)
{
    if (k == 1)
    {
        // gen được 1 hoán vị, tính chi phí, nếu rẻ hơn thì update kết quả
        int cost = calculateRouteCost(costs, route);
        if (cost < minRet)
        {
            minRet = cost;
        }
    }
    else
    {
        for (int i = 0; i < k; ++i)
        {
            genPermutation(k - 1, array, costs, route, minRet);

            if (k % 2 == 0)
            {
                swap(array[i], array[k - 1]);
            }
            else
            {
                swap(array[0], array[k - 1]);
            }
        }
    }
}

int CharlietheDog(vector<string> strArr)
{
    auto positionList = matrixToList(strArr);
    auto costMatrix = initCostMatrix(positionList);
    vector<int> route;

    // init first route: 0 1 2 3 .. n with 0 is the position of the dog, n is the position of the home.
    for (int i = 0; i < positionList.size(); ++i)
    {
        route.push_back(i);
    }

    int minRet = MAX;
    genPermutation(route.size() - 2, route.data() + 1, costMatrix, route, minRet);

    return minRet;
}

void runTest(vector<string> strArr, int expectedResult)
{
    cout << "Map: " << strArr[0] << " " << strArr[1] << " " << strArr[2] << " " << strArr[3] << "\n";
    int result = CharlietheDog(strArr);
    cout << "Result: " << result << "\n";
    cout << "Verdict: " << (result == expectedResult ? "PASSED" : "FAILED") << "\n"
         << endl;
}

int main()
{
    runTest({"FOOF", "OCOO", "OOOH", "FOOO"}, 11);
    runTest({"FOOF", "OHOO", "OOOC", "FOOO"}, 11);
    runTest({"OOOO", "OOFF", "OCHO", "OFOO"}, 7);
    runTest({"OOOO", "OOFF", "OHCO", "OFOO"}, 7);
    runTest({"FOOO", "OCOH", "OFOF", "OFOO"}, 10);
    runTest({"FOOO", "OHOC", "OFOF", "OFOO"}, 10);
    return 0;
}

hanmai@hanubuntu22:~/han/test$ g++ -o out CharlietheDog.cpp
hanmai@hanubuntu22:~/han/test$ ./out
Map: FOOF OCOO OOOH FOOO
Result: 11
Verdict: PASSED

Map: FOOF OHOO OOOC FOOO
Result: 11
Verdict: PASSED

Map: OOOO OOFF OCHO OFOO
Result: 7
Verdict: PASSED

Map: OOOO OOFF OHCO OFOO
Result: 7
Verdict: PASSED

Map: FOOO OCOH OFOF OFOO
Result: 10
Verdict: PASSED

Map: FOOO OHOC OFOF OFOO
Result: 10
Verdict: PASSED