Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <cmath>
- #include <cstdlib>
- #include <fstream>
- #include <iostream>
- #include <vector>
- using namespace std;
- struct Node
- {
- vector<vector<int>> curState;
- int H, G, N;
- string action;
- Node* parent;
- Node(vector<vector<int>> X, string Action, int g, int h, int n, Node* Parent)
- {
- this->curState = X;
- this->action = Action;
- this->G = g;
- this->N = n;
- this->H = h;
- this->parent = Parent;
- }
- };
- int getInversion(vector<int> arr)
- {
- int inv_count = 0;
- for (unsigned int i = 0; i < arr.size() - 1; ++i)
- {
- for (unsigned int j = i + 1; j < arr.size(); ++j)
- {
- inv_count += ((arr[i] > arr[j]) ? 1 : 0);
- }
- }
- return inv_count;
- }
- bool isSolvable(vector<vector<int>> curState, int N)
- {
- int empty_row = -1;
- vector<int> arr;
- for (int i = 0; i < N; ++i)
- {
- for (int j = 0; j < N; ++j)
- {
- if (curState[i][j])
- arr.push_back(curState[i][j]);
- else empty_row = i;
- }
- }
- int inversions = getInversion(arr);
- if (N % 2 == 0 && (empty_row % 2 == !(inversions % 2)))
- return true;
- if (N % 2 == 1 && inversions % 2 == 0)
- return true;
- return false;
- }
- void printData(vector<vector<int>> curState, string outputFilePath)
- {
- int N = curState.size();
- ofstream fout(outputFilePath, ios::out | ios::app);
- for (int i = 0; i < N; ++i)
- {
- for (int j = 0; j < N; ++j)
- {
- fout << curState[i][j] << " ";
- }
- fout << endl;
- }
- fout << endl;
- fout.close();
- }
- void getEmptyPosition(vector<vector<int>> curState, int& xPoz, int& yPoz)
- {
- for (unsigned int i = 0; i < curState.size(); ++i)
- {
- for (unsigned int j = 0; j < curState.size(); ++j)
- {
- if (curState[i][j] == 0)
- {
- xPoz = i, yPoz = j;
- return;
- }
- }
- }
- }
- bool canMoveUp(vector<vector<int>> curState, int N, int xPoz, int yPoz)
- {
- for (int i = 0; i < N; ++i)
- {
- if (curState[xPoz][yPoz] == curState[0][i])
- return false;
- }
- return true;
- }
- bool canMoveDown(vector<vector<int>> curState, int N, int xPoz, int yPoz)
- {
- for (int i = 0; i < N; ++i)
- {
- if (curState[xPoz][yPoz] == curState[N - 1][i])
- return false;
- }
- return true;
- }
- bool canMoveLeft(vector<vector<int>> curState, int N, int xPoz, int yPoz)
- {
- for (int i = 0; i < N; ++i)
- {
- if (curState[xPoz][yPoz] == curState[i][0])
- return false;
- }
- return true;
- }
- bool canMoveRight(vector<vector<int>> curState, int N, int xPoz, int yPoz)
- {
- for (int i = 0; i < N; ++i)
- {
- if (curState[xPoz][yPoz] == curState[i][N - 1])
- return false;
- }
- return true;
- }
- void expandState(vector<vector<int>> curState, int N, vector<vector<int>>& child1, vector<vector<int>>& child2, vector<vector<int>>& child3, vector<vector<int>>& child4)
- {
- int xPoz, yPoz;
- getEmptyPosition(curState, xPoz, yPoz);
- if (canMoveUp(curState, N, xPoz, yPoz))
- {
- child1 = curState;
- swap(child1[xPoz - 1][yPoz], child1[xPoz][yPoz]);
- }
- if (canMoveDown(curState, N, xPoz, yPoz))
- {
- child2 = curState;
- swap(child2[xPoz + 1][yPoz], child2[xPoz][yPoz]);
- }
- if (canMoveLeft(curState, N, xPoz, yPoz))
- {
- child3 = curState;
- swap(child3[xPoz][yPoz - 1], child3[xPoz][yPoz]);
- }
- if (canMoveRight(curState, N, xPoz, yPoz))
- {
- child4 = curState;
- swap(child4[xPoz][yPoz + 1], child4[xPoz][yPoz]);
- }
- }
- int getManhattanDistance(vector<vector<int>>curState, vector<vector<int>> goalState, int N)
- {
- int manhattan = 0;
- for (int i = 0; i < N; ++i)
- {
- for (int j = 0; j < N; ++j)
- {
- if (i == N - 1 && j == N - 1)
- {
- break;
- }
- for (int x = 0; x < N; ++x)
- {
- for (int y = 0; y < N; ++y)
- {
- if (goalState[i][j] == curState[x][y])
- manhattan = manhattan + abs(i - x) + abs(j - y);
- }
- }
- }
- }
- return manhattan;
- }
- void getChilds(Node curState, int N, vector<Node>& Tree, string outputFilePath, vector<vector<int>> goalState)
- {
- vector<vector<int>> child1, child2, child3, child4;
- expandState(curState.curState, N, child1, child2, child3, child4);
- int H;
- if (!child1.empty())
- {
- H = getManhattanDistance(child1, goalState, N);
- Tree.push_back(Node(child1, "UP", curState.G + 1, H, N, &curState));
- }
- if (!child2.empty())
- {
- H = getManhattanDistance(child2, goalState, N);
- Tree.push_back(Node(child2, "DOWN", curState.G + 1, H, N, &curState));
- }
- if (!child3.empty())
- {
- H = getManhattanDistance(child3, goalState, N);
- Tree.push_back(Node(child3, "LEFT", curState.G + 1, H, N, &curState));
- }
- if (!child4.empty())
- {
- H = getManhattanDistance(child4, goalState, N);
- Tree.push_back(Node(child4, "RIGHT", curState.G + 1, H, N, &curState));
- }
- }
- bool checkForDuplicate(Node node, vector<Node> List)
- {
- for (auto itr = List.begin(); itr < List.end(); ++itr)
- {
- if (node.curState == itr->curState)
- return true;
- }
- return false;
- }
- bool operator <(Node A, Node B)
- {
- return A.H + A.G < B.H + B.G;
- }
- void aStar(Node input, vector<vector<int>> goalState, int N, string outputFilePath)
- {
- vector<Node> openList, closedList;
- openList.push_back(input);
- while (!openList.empty())
- {
- auto min = min_element(openList.begin(), openList.end());
- Node curNode = *min;
- if (curNode.curState == goalState || curNode.H == 0)
- {
- cout << curNode.G << endl;
- printData(curNode.curState, outputFilePath);
- // while (curNode.parent != nullptr)
- // {
- // printData(curNode.parent->curState, outputFilePath);
- // curNode = *(curNode.parent);
- // }
- /*
- ^
- |
- asta nu functioneaza, n-am stiut cum sa revin la parinti
- */
- return;
- }
- openList.erase(min);
- closedList.push_back(curNode);
- vector<Node> Tree;
- getChilds(curNode, N, Tree, outputFilePath, goalState);
- for (unsigned int i = 0; i < Tree.size(); ++i)
- {
- if (checkForDuplicate(Tree[i], closedList))
- continue;
- if (!checkForDuplicate(Tree[i], openList))
- {
- openList.push_back(Tree[i]);
- }
- }
- }
- }
- bool checkCorrectData(vector<vector<int>> mat)
- {
- vector<int> freq(mat.size() * mat.size(), 0);
- for (unsigned int i = 0; i < mat.size(); ++i)
- {
- for (unsigned int j = 0; j < mat.size(); ++j)
- {
- freq[mat[i][j]]++;
- }
- }
- for (unsigned int i = 0; i < mat.size() * mat.size(); ++i)
- {
- if (freq[i] != 1)
- return true;
- }
- return false;
- }
- Node readData(string filePath, int& N, vector<vector<int>>& goalState)
- {
- vector<vector<int>> givenState;
- cout << "Care este calea fisierului de intrare: ";
- cin >> filePath;
- ifstream fin;
- fin.open(filePath, ios::in);
- if (!fin)
- {
- cerr << "Eroare la deschiderea fisierului " << filePath;
- exit(EXIT_FAILURE);
- }
- fin >> N;
- if (N <= 1)
- {
- cerr << "Dimensiunea puzzle-ului trebuie sa fie minim 2!";
- exit(EXIT_FAILURE);
- }
- vector<vector<int>> X(N, vector<int>(N));
- goalState.resize(N, vector<int>(N));
- for (int i = 0; i < N; ++i)
- {
- for (int j = 0; j < N; ++j)
- {
- fin >> X[i][j];
- if (X[i][j] < 0 || X[i][j] >= (N * N))
- {
- cerr << "Elementele introduse au fost invalide. Introduceti doar valori intre 0 si " << N * N - 1;
- exit(EXIT_FAILURE);
- }
- goalState[i][j] = (N * i + j + 1) % (N * N);
- }
- }
- if (checkCorrectData(X))
- {
- cerr << "Elementele introduse au fost invalide. Introduceti doar valori intre 0 si " << N * N - 1;
- exit(EXIT_FAILURE);
- }
- Node input(X, "None", 0, 0, N, nullptr);
- int H = getManhattanDistance(input.curState, goalState, N);
- input.H = H;
- fin.close();
- return input;
- }
- int main()
- {
- int N;
- string inputFilePath, outputFilePath;
- vector<vector<int>> goalState;
- Node input = readData(inputFilePath, N, goalState);
- cout << "Care este calea fisierului de iesire: "; cin >> outputFilePath;
- if (isSolvable(input.curState, N))
- {
- aStar(input, goalState, N, outputFilePath);
- return 0;
- }
- else
- {
- cerr << "Puzzle-ul introdus nu este rezolvabil!";
- exit(EXIT_FAILURE);
- }
- }
Add Comment
Please, Sign In to add comment