Advertisement
wurdalak007

Untitled

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