SHARE
TWEET

Untitled

a guest Sep 18th, 2019 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <map>
  3. #include <string>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <queue>
  7.  
  8. #include <stdio.h>
  9. #include <time.h>
  10. using namespace std;
  11.  
  12. int dx[] = { 1, -1, 3, -3 };
  13.  
  14. map<string, int> strtoind;
  15. map<int, string> indtostr;
  16.  
  17. string ansstr = "XAMELEON.";
  18. int index = 0;
  19. int cntdiff(string s) {
  20.     int firstlet = -1, firstmeet = -1;
  21.     int cnt = 0;
  22.     for (int i = 0; i < s.size(); i++) {
  23.         if (s[i] != ansstr[i]) {
  24.             int ind = 0;
  25.             for (int j = 0; ansstr.size(); j++) {
  26.                 if (ansstr[j] == s[i]) {
  27.                     if (s[i] == 'E') {
  28.                         if (firstmeet == 1 && i > firstlet) {
  29.                             ind = j;
  30.                             break;
  31.                         }
  32.                         else {
  33.                             firstmeet = 1;
  34.                             firstlet = i;
  35.                             ind = j;
  36.                             break;
  37.                         }
  38.                     }
  39.                     ind = j;
  40.                     break;
  41.                 }
  42.             }
  43.  
  44.             cnt += abs(ind % 3 - i % 3) + abs(ind / 3 - i / 3);
  45.         }
  46.     }
  47.     return cnt;
  48. }
  49.  
  50. bool cmp(pair<int, int> a, pair<int, int> b) {
  51.     if (a.first == b.first)
  52.         return a.second > b.second;
  53.     else return a.first > b.first;
  54. }
  55. void bfs(string cur, vector<int>& p, vector<int>& was, vector<int>& steps) {
  56.     priority_queue<pair<int, int>, vector<pair<int, int>>, bool(*)(pair<int, int>, pair<int, int>)> pq(cmp);
  57.     if (strtoind.count(cur) == 0) {
  58.         strtoind[cur] = index;
  59.         indtostr[index] =cur;
  60.         index++;
  61.         was.push_back(0);
  62.         p.push_back(0);
  63.         steps.push_back(0);
  64.     }
  65.     was[strtoind[cur]] = 1;
  66.  
  67.     pq.push({ cntdiff(cur), strtoind[cur] });
  68.  
  69.     while (!pq.empty()) {
  70.         auto po = pq.top();
  71.         pq.pop();
  72.         int ind = po.second;
  73.         int x = -1;
  74.         cur = indtostr[ind];
  75.         for (int i = 0; i < 9; i++) {
  76.  
  77.             if (cur[i] == '.') {
  78.                 x = i;
  79.                 break;
  80.             }
  81.  
  82.         }
  83.         //cout << "q.front = " << indtostr[ind] << endl;
  84.         for (int i = 0; i < 4; i++) {
  85.             int nx = x + dx[i];
  86.             if (nx >= 0 && nx < 9) {
  87.                 if (x % 3 == 2 && dx[i] == 1 || x % 3 == 0 && dx[i] == -1)
  88.                     continue;
  89.                 string t = cur;
  90.  
  91.                 swap(t[x], t[nx]);
  92.                 if (strtoind.count(t) == 0) {
  93.                     strtoind[t] = index;
  94.                     indtostr[index] = t;
  95.                     index++;
  96.                     was.push_back(0);
  97.                     p.push_back(0);
  98.                     steps.push_back(0);
  99.                 }
  100.                 int nind = strtoind[t];
  101.                 if (!was[nind]) {
  102.                     //cout << "new string t = " << t;
  103.                     was[nind] = 1;
  104.                     pq.push({ cntdiff(t), nind });
  105.                     p[nind] = strtoind[cur];
  106.                     //cout << "   p[nind] = " << p[nind] << "     ";
  107.                     steps[nind] = steps[strtoind[cur]] + 1;
  108.                     //cout << "   steps[nind] = " << steps[nind] << endl;
  109.                     if (t == ansstr)
  110.                         return;
  111.                 }
  112.             }
  113.         }
  114.     }
  115. }
  116.  
  117. int main() {
  118.    
  119.     indtostr[0] = ansstr;
  120.     strtoind[ansstr] = 0;
  121.     index++;
  122.  
  123.     cout << "Enter the combination:\n";
  124.  
  125.     vector<int> pred(index), was(index), steps(index);
  126.  
  127.     string t;
  128.     for (int i = 0; i < 3; i++) {
  129.         string te;
  130.         cin >> te;
  131.         t += te;
  132.     }
  133.     if (t == ansstr) {
  134.         cout << "That's the answer";
  135.         return 0;
  136.     }
  137.     clock_t start = clock();
  138.     bfs(t, pred, was, steps);
  139.  
  140.     if (steps[strtoind[ansstr]] == 0) {
  141.         cout << "No solution";
  142.         return 0;
  143.     }
  144.  
  145.     vector<int> ans;
  146.  
  147.     index = strtoind[ansstr];
  148.  
  149.     while (index != strtoind[t]) {
  150.         ans.push_back(index);
  151.         index = pred[index];
  152.     }
  153.  
  154.     reverse(begin(ans), end(ans));
  155.  
  156.  
  157.     for (int i = 0; i < ans.size(); i++) {
  158.         string t = indtostr[ans[i]];
  159.         for (int i = 0; i < 9; i += 3) {
  160.             for (int j = 0; j < 3; j++)
  161.                 cout << t[i + j];
  162.             cout << endl;
  163.         }
  164.         cout << endl;
  165.     }
  166.  
  167.     clock_t end = clock();
  168.     double seconds = (double)(end - start) / CLOCKS_PER_SEC;
  169.     cout << "time: " << seconds << endl << endl;
  170.     cout << "You need " <<  steps[strtoind[ansstr]] << " step(s)" << endl;
  171.  
  172.  
  173.     return 0;
  174. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top