Advertisement
wurdalak007

Untitled

Mar 14th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.34 KB | None | 0 0
  1. //
  2. // main.cpp
  3. // Пятнашки
  4. //
  5. // Created by Матвей on 12.03.2018.
  6. // Copyright © 2018 Матвей. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10. #include <vector>
  11. #include <queue>
  12. #include <map>
  13. #include <set>
  14. #include <cassert>
  15.  
  16.  
  17. using namespace std;
  18.  
  19. const int inf = 10000000;
  20.  
  21. class Graph{
  22. public:
  23. struct Vertex{
  24. vector<int> Condition;
  25. int depth;
  26. int heuristic;
  27. Vertex* parent;
  28. char WhichMove;
  29. };
  30.  
  31. Graph(vector<int>& Start);
  32. void RestoreTheWay();
  33. bool Compare( const Graph::Vertex& first, const Graph::Vertex& second );
  34. void GetNextVertex(Vertex& Start, vector<Vertex>& NextVert );
  35. void PrintAnswer();
  36. bool IsFinalCondition(Vertex v);
  37. int CountTheHeuristic( Vertex v );
  38. Vertex AStar();
  39.  
  40. private:
  41. Vertex Start;
  42. string Way;
  43. int NumOfMoves;
  44. };
  45.  
  46. bool operator<( const Graph::Vertex first, const Graph::Vertex second )
  47. {
  48. return first.depth > second.depth;
  49. }
  50.  
  51. void Graph::PrintAnswer(){
  52. cout << NumOfMoves << endl;
  53. for( int i = 0; i < Way.length(); i++ )
  54. cout << Way[i];
  55. }
  56.  
  57. void Graph::RestoreTheWay(){
  58. string ReverseWay;
  59. NumOfMoves = 0;
  60. Vertex Final = AStar();
  61. Vertex* tmp = &Final;
  62. while( tmp->parent != nullptr ) {
  63. ReverseWay += Final.WhichMove;
  64. NumOfMoves += 1;
  65. tmp = tmp->parent;
  66. }
  67.  
  68. for( int i = (int)ReverseWay.length()-1; i >=0; i-- ) {
  69. Way += ReverseWay[i];
  70. }
  71.  
  72. }
  73.  
  74.  
  75. Graph::Vertex Graph::AStar()
  76. {
  77. priority_queue<Vertex, vector<Vertex>, less<Vertex>> q;
  78. map<Vertex, int> used;
  79. used.insert(make_pair(Start, 0));
  80. q.push(Start);
  81.  
  82. while( !q.empty() ) {
  83. Vertex tmp = q.top();
  84. q.pop();
  85.  
  86. if( IsFinalCondition(tmp) ) return tmp;
  87.  
  88. vector<Vertex> NextVert;
  89. GetNextVertex(tmp, NextVert);
  90.  
  91. for( auto v : NextVert ) {
  92. int new_cost = used[tmp] + 1;
  93. Vertex* parent = &tmp;
  94. v.parent = parent;
  95. if( used.find(v) != used.end() || new_cost < used[v] ) {
  96. used.insert(make_pair(v, new_cost));
  97. v.depth = new_cost + v.heuristic;
  98. q.push(v);
  99. }
  100. }
  101.  
  102. }
  103.  
  104. assert(1 == 2);
  105. return Start;
  106. }
  107.  
  108. Graph::Graph( vector<int>& StartCondition )
  109. {
  110. for(auto i : StartCondition){
  111. Start.Condition.push_back(i);
  112. }
  113. Start.depth = 0;
  114. Start.heuristic = CountTheHeuristic(Start);
  115. Start.parent = nullptr;
  116. Start.WhichMove = '0';
  117. }
  118.  
  119. int Graph::CountTheHeuristic(Vertex v)
  120. {
  121. int Heuristic = 0;
  122. for( int i = 0; i < v.Condition.size(); i++ ) {
  123. int elem = v.Condition[i];
  124. if( i == 15 && elem == 0) {
  125. Heuristic += 0;
  126. } else {
  127. Heuristic += (abs(elem-1-i)/4)+(abs(elem-1-i)%4);
  128. }
  129. }
  130. return Heuristic;
  131. }
  132.  
  133. bool Graph::IsFinalCondition(Vertex v)
  134. {
  135. for( int i = 1; i <= v.Condition.size(); i++ ) {
  136. if( i != v.Condition.size() ) {
  137. if( i != v.Condition[i-1] ) return false;
  138. } else {
  139. if( v.Condition[i-1] != 0 ) return false;
  140. }
  141. }
  142. return true;
  143. }
  144.  
  145. void Graph::GetNextVertex(Vertex& start, vector<Vertex>& NextVert)
  146. {
  147. int SpacePosition = 0;
  148. for( int i = 0; i < (int)start.Condition.size(); i++ ) {
  149. if( start.Condition[i] == 0 ){
  150. SpacePosition = i;
  151. break;
  152. }
  153. }
  154.  
  155. if( SpacePosition < start.Condition.size() - 1 ) {
  156. Vertex* tmp = new Vertex;
  157. tmp->Condition.resize(start.Condition.size());
  158. for( int i = 0; i < start.Condition.size(); i++ ) {
  159. tmp->Condition[i] = start.Condition[i];
  160. }
  161. swap(tmp->Condition[SpacePosition], tmp->Condition[SpacePosition+1]);
  162. int heuristic = CountTheHeuristic(*(tmp));
  163. tmp->heuristic = heuristic;
  164. tmp->WhichMove = 'R';
  165. tmp->depth = inf;
  166. if( tmp != &start ) {
  167. // tmp->parent = &start;
  168. NextVert.push_back(*(tmp));
  169. } else {
  170. delete tmp;
  171. }
  172. }
  173.  
  174. if( SpacePosition > 0 ){
  175. Vertex* tmp = new Vertex;
  176. tmp->Condition.resize(Start.Condition.size());
  177. for( int i = 0; i < Start.Condition.size(); i++ ) {
  178. tmp->Condition[i] = Start.Condition[i];
  179. }
  180. swap(tmp->Condition[SpacePosition],tmp->Condition[SpacePosition-1]);
  181. int heuristic = CountTheHeuristic(*(tmp));
  182. tmp->heuristic = heuristic;
  183. tmp->depth = inf;
  184. tmp->WhichMove = 'L';
  185. if( tmp != &start ) {
  186. // tmp->parent = &start;
  187. NextVert.push_back(*(tmp));
  188. } else {
  189. delete tmp;
  190. }
  191. }
  192.  
  193. if( SpacePosition >= 4 ){
  194. Vertex* tmp = new Vertex;
  195. tmp->Condition.resize(Start.Condition.size());
  196. for( int i = 0; i < Start.Condition.size(); i++ ) {
  197. tmp->Condition[i] = Start.Condition[i];
  198. }
  199. swap(tmp->Condition[SpacePosition],tmp->Condition[SpacePosition-4]);
  200. int heuristic = CountTheHeuristic(*(tmp));
  201. tmp->heuristic = heuristic;
  202. tmp->WhichMove = 'U';
  203. tmp->depth = inf;
  204. if( tmp != &start ) {
  205. // tmp->parent = &start;
  206. NextVert.push_back(*(tmp));
  207. } else {
  208. delete tmp;
  209. }
  210. }
  211.  
  212. if( SpacePosition <= Start.Condition.size() - 5 ){
  213. Vertex* tmp = new Vertex;
  214. tmp->Condition.resize(Start.Condition.size());
  215. for( int i = 0; i < Start.Condition.size(); i++ ) {
  216. tmp->Condition[i] = Start.Condition[i];
  217. }
  218. swap(tmp->Condition[SpacePosition],tmp->Condition[SpacePosition+4]);
  219. int heuristic = CountTheHeuristic(*(tmp));
  220. tmp->heuristic = heuristic;
  221. tmp->WhichMove = 'D';
  222. tmp->depth = inf;
  223. if( tmp != &start ) {
  224. // tmp->parent = &start;
  225. NextVert.push_back(*(tmp));
  226. } else {
  227. delete tmp;
  228. }
  229. }
  230.  
  231. }
  232.  
  233. int main() {
  234. vector<int> g;
  235. for( int i = 0; i < 16; i++ ) {
  236. int tmp = 0;
  237. cin >> tmp;
  238. g.push_back(tmp);
  239. }
  240. Graph graph(g);
  241. graph.RestoreTheWay();
  242. graph.PrintAnswer();
  243. return 0;
  244. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement