Created
May 8, 2023 07:48
-
-
Save maixuanhan/2d9ba47873db5f43884cc1b884a24c2a to your computer and use it in GitHub Desktop.
Giải bài CharlietheDog bằng sinh hoán vị
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Author
maixuanhan
commented
May 8, 2023
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment