Guest User

Untitled

a guest
Dec 14th, 2019
103
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <assert.h>
  4. #include <string>
  5. #include <time.h>
  6.  
  7.  
  8. enum Sides {
  9. U,
  10. D,
  11. L,
  12. R
  13. };
  14.  
  15. class P {
  16. private:
  17.  
  18. std::vector <short int> mat;
  19. public:
  20.  
  21. int parent;
  22.  
  23. int step;
  24.  
  25. Sides Side;
  26.  
  27. P() {}
  28.  
  29. P(std::vector<short int> m, int s, Sides tmp, int p) : mat{ m }, step{ s }, Side{ tmp }, parent{ p } {}
  30.  
  31. int f();
  32.  
  33. int g();
  34.  
  35. int h();
  36.  
  37. bool equal(P second);
  38.  
  39. bool operator>(P second);
  40.  
  41. bool operator<(P second);
  42.  
  43. bool operator==(P second);
  44.  
  45. int ExistenceOfSolutions();
  46.  
  47. std::vector<P> ReturnNext(int number);
  48.  
  49. void Print_P();
  50.  
  51. unsigned long long int hesh();
  52. };
  53.  
  54.  
  55. unsigned long long int P::hesh() {
  56. unsigned long long int res = 0;
  57. for (unsigned long long int i = 0, pow = 1; i < 9; i++, pow *= 9) {
  58. res += mat.at(i) * pow;
  59. }
  60. return res;
  61. }
  62.  
  63.  
  64. void P::Print_P() {
  65. std::cout << "g: " << this->g() << " h: " << this->h() << std::endl;
  66. for (int i = 0; i < 9; ++i) {
  67. std::cout << this->mat.at(i) << ' ';
  68. }
  69. std::cout << std::endl;
  70. }
  71.  
  72.  
  73. int P::f() {
  74. return this->g() + this->h();
  75. }
  76.  
  77.  
  78.  
  79. int P::h() {
  80. int N{ 3 }, res{ 0 };
  81. for (int i = 0; i < N * N; ++i)
  82. if (mat.at(i) != 0)
  83. res += abs((mat.at(i) - 1) / N - i / N) + abs((mat.at(i) - 1) - ((mat.at(i) - 1) / N) * N - (i - (i / N) * N));
  84. for (int i = 0; i < N; ++i){
  85. int max = -1;
  86. for (int j = 0; j < N; ++j){
  87. if (mat.at(i * N + j) != 0 && (mat.at(i * N + j) - 1) / N == i){
  88. if (mat.at(i * N + j) > max) max = mat.at(i * N + j);
  89. else res += 2;
  90. }
  91. }
  92. }
  93. for (int j = 0; j < N; ++j){
  94. int max = -1;
  95. for (int i = 0; i < N; ++i)
  96. if (mat.at(i * N + j) != 0 && mat.at(i * N + j) % N == j + 1) {
  97. if (mat.at(i * N + j) > max) max = mat.at(i * N + j);
  98. else res += 2;
  99. }
  100. }
  101. return -1 * res;
  102. }
  103.  
  104.  
  105. int P::g() {
  106. return -(this->step);
  107. }
  108.  
  109.  
  110. bool P::equal(P second) {
  111. for (int i = 0; i < 9; ++i)
  112. if (!(this->mat.at(i) == second.mat.at(i))) return false;
  113. return true;
  114. }
  115.  
  116.  
  117. bool P::operator==(P second) {
  118. return this->f() == second.f();
  119. }
  120.  
  121.  
  122. bool P::operator>(P second) {
  123. return this->f() > second.f();
  124. }
  125.  
  126.  
  127. bool P::operator<(P second) {
  128. return this->f() < second.f();
  129. }
  130.  
  131.  
  132. class Priority_Queue {
  133. private:
  134.  
  135. std::vector<P> heap;
  136.  
  137. public:
  138.  
  139. Priority_Queue() {}
  140.  
  141. ~Priority_Queue() {}
  142.  
  143. void AddDigit(P digit);
  144.  
  145. void SiftDown(int num);
  146.  
  147. P ExtractMax();
  148.  
  149. bool empty() { return heap.size(); }
  150.  
  151. void Print_Queue();
  152. };
  153.  
  154.  
  155. void Priority_Queue::Print_Queue() {
  156. for (int i = 0; i < 10; ++i) std::cout << '-';
  157. std::cout << std::endl;
  158. for (int i = 0; i < heap.size(); ++i) {
  159. heap.at(i).Print_P();
  160. }
  161. for (int i = 0; i < 10; ++i) std::cout << '-';
  162. std::cout << std::endl;
  163. }
  164.  
  165.  
  166. void Priority_Queue::AddDigit(P digit) {
  167. heap.push_back(digit);
  168. int index = heap.size() - 1;
  169. int parent = (index - 1) / 2;
  170.  
  171. while (index > 0 && heap.at(parent) < heap.at(index)) {
  172. std::swap(heap.at(index), heap.at(parent));
  173. index = parent;
  174. parent = (index - 1) / 2;
  175. }
  176.  
  177. }
  178.  
  179.  
  180. void Priority_Queue::SiftDown(int num) {
  181. int leftChild;
  182. int rightChild;
  183. int largestChild;
  184.  
  185. for (;;)
  186. {
  187. leftChild = 2 * num + 1;
  188. rightChild = 2 * num + 2;
  189. largestChild = num;
  190.  
  191. if (leftChild < heap.size() && heap.at(leftChild) > heap.at(largestChild))
  192. {
  193. largestChild = leftChild;
  194. }
  195.  
  196. if (rightChild < heap.size() && heap.at(rightChild) > heap.at(largestChild))
  197. {
  198. largestChild = rightChild;
  199. }
  200.  
  201. if (largestChild == num)
  202. {
  203. break;
  204. }
  205.  
  206. std::swap(heap.at(num), heap.at(largestChild));
  207. num = largestChild;
  208. }
  209. }
  210.  
  211.  
  212. P Priority_Queue::ExtractMax() {
  213. assert(!heap.empty());
  214.  
  215. P result = heap.at(0);
  216.  
  217. heap.at(0) = heap.at(heap.size() - 1);
  218.  
  219. heap.resize(heap.size() - 1);
  220.  
  221. if (!heap.empty())
  222. this->SiftDown(0);
  223. return result;
  224. }
  225.  
  226.  
  227. std::vector<P> P::ReturnNext(int number) {
  228. int r_i{ 0 };
  229. for (int i = 0; i < 9; ++i)
  230. if (mat.at(i) == 0) r_i = i;
  231.  
  232. std::vector<P> res;
  233.  
  234. if (r_i < 6) {
  235. std::vector<short int> tmp_mat = this->mat;
  236. std::swap(tmp_mat.at(r_i), tmp_mat.at(r_i + 3));
  237. P tmp{ tmp_mat, this->step + 1, D, number };
  238. res.push_back(tmp);
  239. }
  240.  
  241. if (r_i > 2) {
  242. std::vector<short int> tmp_mat = this->mat;
  243. std::swap(tmp_mat.at(r_i), tmp_mat.at(r_i - 3));
  244. P tmp{ tmp_mat, this->step + 1, U, number };
  245. res.push_back(tmp);
  246. }
  247.  
  248. if (r_i % 3 != 0) {
  249. std::vector<short int> tmp_mat = this->mat;
  250. std::swap(tmp_mat.at(r_i), tmp_mat.at(r_i - 1));
  251. P tmp{ tmp_mat, this->step + 1, L, number };
  252. res.push_back(tmp);
  253. }
  254.  
  255. if (r_i % 3 != 2) {
  256. std::vector<short int> tmp_mat = this->mat;
  257. std::swap(tmp_mat.at(r_i), tmp_mat.at(r_i + 1));
  258. P tmp{ tmp_mat, this->step + 1, R, number };
  259. res.push_back(tmp);
  260. }
  261.  
  262. return res;
  263. }
  264.  
  265.  
  266. std::vector<P> DeleteEntryInSecond(std::vector<P> to, std::vector<unsigned long long int> second) {
  267. std::vector<P> res;
  268. for (int i = 0; i < to.size(); ++i) {
  269. bool tmp = true;
  270. unsigned long long int chesh = to.at(i).hesh();
  271. for (int j = 0; j < second.size(); ++j) {
  272. if (chesh == second.at(j)) {
  273. tmp = false;
  274. break;
  275. }
  276. }
  277. if (tmp == true) res.push_back(to.at(i));
  278. }
  279. return res;
  280. }
  281.  
  282.  
  283. int P::ExistenceOfSolutions() {
  284. int N = 0;
  285. for (int i = 0; i < 9; ++i)
  286. if (this->mat.at(i) != 0) {
  287. for (int z = 0; z < i; ++z)
  288. if (mat.at(z) > mat.at(i)) N++;
  289. }
  290. if (N % 2 != 0) return -1;
  291. return N;
  292. }
  293.  
  294.  
  295. void alg_A_zvz(P enter) {
  296. int res = enter.ExistenceOfSolutions();
  297. if (res == -1) {
  298. std::cout << res << std::endl;
  299. return;
  300. }
  301.  
  302. std::vector<unsigned long long int> closed;
  303. std::vector < std::pair<Sides, short int>> closed_1;
  304. Priority_Queue open;
  305. P current = enter;
  306. closed.push_back(current.hesh());
  307. closed_1.push_back(std::make_pair(U, -1));
  308. open.AddDigit(enter);
  309.  
  310. std::vector<short int> d;
  311. for (int i = 0; i < 8; ++i) {
  312. d.push_back(i + 1);
  313. }
  314. d.push_back(0);
  315. P des{ d, 0, U, -1 };
  316.  
  317. if (des == current) {
  318. std::cout << 0 << std::endl;
  319. return;
  320. }
  321. while (!(current.equal(des))) {
  322. current = open.ExtractMax();
  323. closed.push_back(current.hesh());
  324. closed_1.push_back(std::make_pair(current.Side, current.parent));
  325. std::vector<P> to = DeleteEntryInSecond(current.ReturnNext(closed.size() - 1), closed);
  326. for (int i = 0; i < to.size(); ++i) {
  327. open.AddDigit(to.at(i));
  328. }
  329.  
  330. }
  331.  
  332. std::cout << current.step << std::endl;
  333. int z = closed.size() - 1;
  334. std::string ress = "";
  335. while (z != -1) {
  336. int tmp = closed_1.at(z).first;
  337. z = closed_1.at(z).second;
  338. switch (tmp) {
  339. case 0:
  340. ress += "U";
  341. break;
  342. case 1:
  343. ress += "D";
  344. break;
  345. case 2:
  346. ress += "L";
  347. break;
  348. case 3:
  349. ress += "R";
  350. break;
  351. }
  352. }
  353. for (int i = ress.size() - 2; i >= 0; i--) std::cout << ress[i];
  354. }
  355.  
  356.  
  357. int main()
  358. {
  359. std::vector<short int> ent;
  360.  
  361. for (int i = 0; i < 9; ++i) {
  362. short int tmp;
  363. std::cin >> tmp;
  364. ent.push_back(tmp);
  365. }
  366.  
  367. P enter{ ent, 0, U, -1 };
  368. //time_t start, end;
  369. //time(&start);
  370. alg_A_zvz(enter);
  371. //time(&end);
  372. //std::cout << std::endl << "T: " << difftime(end, start) << std::endl;
  373. //system("pause");
  374. return 0;
  375. }
RAW Paste Data