Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // main.cpp
- // Пятнашки
- //
- // Created by Матвей on 12.03.2018.
- // Copyright © 2018 Матвей. All rights reserved.
- //
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <map>
- #include <set>
- #include <cassert>
- using namespace std;
- const int inf = 10000000;
- class Graph{
- public:
- struct Vertex{
- vector<int> Condition;
- int depth;
- int heuristic;
- Vertex* parent;
- char WhichMove;
- };
- Graph(vector<int>& Start);
- void RestoreTheWay();
- bool Compare( const Graph::Vertex& first, const Graph::Vertex& second );
- void GetNextVertex(Vertex& Start, vector<Vertex>& NextVert );
- void PrintAnswer();
- bool IsFinalCondition(Vertex v);
- int CountTheHeuristic( Vertex v );
- Vertex AStar();
- private:
- Vertex Start;
- string Way;
- int NumOfMoves;
- };
- bool operator<( const Graph::Vertex first, const Graph::Vertex second )
- {
- return first.depth > second.depth;
- }
- void Graph::PrintAnswer(){
- cout << NumOfMoves << endl;
- for( int i = 0; i < Way.length(); i++ )
- cout << Way[i];
- }
- void Graph::RestoreTheWay(){
- string ReverseWay;
- NumOfMoves = 0;
- Vertex Final = AStar();
- Vertex* tmp = &Final;
- while( tmp->parent != nullptr ) {
- ReverseWay += Final.WhichMove;
- NumOfMoves += 1;
- tmp = tmp->parent;
- }
- for( int i = (int)ReverseWay.length()-1; i >=0; i-- ) {
- Way += ReverseWay[i];
- }
- }
- Graph::Vertex Graph::AStar()
- {
- priority_queue<Vertex, vector<Vertex>, less<Vertex>> q;
- map<Vertex, int> used;
- used.insert(make_pair(Start, 0));
- q.push(Start);
- while( !q.empty() ) {
- Vertex tmp = q.top();
- q.pop();
- if( IsFinalCondition(tmp) ) return tmp;
- vector<Vertex> NextVert;
- GetNextVertex(tmp, NextVert);
- for( auto v : NextVert ) {
- int new_cost = used[tmp] + 1;
- Vertex* parent = &tmp;
- v.parent = parent;
- if( used.find(v) != used.end() || new_cost < used[v] ) {
- used.insert(make_pair(v, new_cost));
- v.depth = new_cost + v.heuristic;
- q.push(v);
- }
- }
- }
- assert(1 == 2);
- return Start;
- }
- Graph::Graph( vector<int>& StartCondition )
- {
- for(auto i : StartCondition){
- Start.Condition.push_back(i);
- }
- Start.depth = 0;
- Start.heuristic = CountTheHeuristic(Start);
- Start.parent = nullptr;
- Start.WhichMove = '0';
- }
- int Graph::CountTheHeuristic(Vertex v)
- {
- int Heuristic = 0;
- for( int i = 0; i < v.Condition.size(); i++ ) {
- int elem = v.Condition[i];
- if( i == 15 && elem == 0) {
- Heuristic += 0;
- } else {
- Heuristic += (abs(elem-1-i)/4)+(abs(elem-1-i)%4);
- }
- }
- return Heuristic;
- }
- bool Graph::IsFinalCondition(Vertex v)
- {
- for( int i = 1; i <= v.Condition.size(); i++ ) {
- if( i != v.Condition.size() ) {
- if( i != v.Condition[i-1] ) return false;
- } else {
- if( v.Condition[i-1] != 0 ) return false;
- }
- }
- return true;
- }
- void Graph::GetNextVertex(Vertex& start, vector<Vertex>& NextVert)
- {
- int SpacePosition = 0;
- for( int i = 0; i < (int)start.Condition.size(); i++ ) {
- if( start.Condition[i] == 0 ){
- SpacePosition = i;
- break;
- }
- }
- if( SpacePosition < start.Condition.size() - 1 ) {
- Vertex* tmp = new Vertex;
- tmp->Condition.resize(start.Condition.size());
- for( int i = 0; i < start.Condition.size(); i++ ) {
- tmp->Condition[i] = start.Condition[i];
- }
- swap(tmp->Condition[SpacePosition], tmp->Condition[SpacePosition+1]);
- int heuristic = CountTheHeuristic(*(tmp));
- tmp->heuristic = heuristic;
- tmp->WhichMove = 'R';
- tmp->depth = inf;
- if( tmp != &start ) {
- // tmp->parent = &start;
- NextVert.push_back(*(tmp));
- } else {
- delete tmp;
- }
- }
- if( SpacePosition > 0 ){
- Vertex* tmp = new Vertex;
- tmp->Condition.resize(Start.Condition.size());
- for( int i = 0; i < Start.Condition.size(); i++ ) {
- tmp->Condition[i] = Start.Condition[i];
- }
- swap(tmp->Condition[SpacePosition],tmp->Condition[SpacePosition-1]);
- int heuristic = CountTheHeuristic(*(tmp));
- tmp->heuristic = heuristic;
- tmp->depth = inf;
- tmp->WhichMove = 'L';
- if( tmp != &start ) {
- // tmp->parent = &start;
- NextVert.push_back(*(tmp));
- } else {
- delete tmp;
- }
- }
- if( SpacePosition >= 4 ){
- Vertex* tmp = new Vertex;
- tmp->Condition.resize(Start.Condition.size());
- for( int i = 0; i < Start.Condition.size(); i++ ) {
- tmp->Condition[i] = Start.Condition[i];
- }
- swap(tmp->Condition[SpacePosition],tmp->Condition[SpacePosition-4]);
- int heuristic = CountTheHeuristic(*(tmp));
- tmp->heuristic = heuristic;
- tmp->WhichMove = 'U';
- tmp->depth = inf;
- if( tmp != &start ) {
- // tmp->parent = &start;
- NextVert.push_back(*(tmp));
- } else {
- delete tmp;
- }
- }
- if( SpacePosition <= Start.Condition.size() - 5 ){
- Vertex* tmp = new Vertex;
- tmp->Condition.resize(Start.Condition.size());
- for( int i = 0; i < Start.Condition.size(); i++ ) {
- tmp->Condition[i] = Start.Condition[i];
- }
- swap(tmp->Condition[SpacePosition],tmp->Condition[SpacePosition+4]);
- int heuristic = CountTheHeuristic(*(tmp));
- tmp->heuristic = heuristic;
- tmp->WhichMove = 'D';
- tmp->depth = inf;
- if( tmp != &start ) {
- // tmp->parent = &start;
- NextVert.push_back(*(tmp));
- } else {
- delete tmp;
- }
- }
- }
- int main() {
- vector<int> g;
- for( int i = 0; i < 16; i++ ) {
- int tmp = 0;
- cin >> tmp;
- g.push_back(tmp);
- }
- Graph graph(g);
- graph.RestoreTheWay();
- graph.PrintAnswer();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement