SHARE
TWEET

Untitled

a guest Sep 18th, 2019 93 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.     queue <int> q;
  58.     if (strtoind.count(cur) == 0) {
  59.         strtoind[cur] = index;
  60.         indtostr[index] = cur;
  61.         index++;
  62.         was.push_back(0);
  63.         p.push_back(0);
  64.         steps.push_back(0);
  65.     }
  66.     was[strtoind[cur]] = 1;
  67.  
  68.     q.push(strtoind[cur]);
  69.  
  70.     while (!q.empty()) {
  71.         auto po = q.front();
  72.         q.pop();
  73.         int ind = po;
  74.         int x = -1;
  75.         cur = indtostr[ind];
  76.         for (int i = 0; i < 9; i++) {
  77.  
  78.             if (cur[i] == '.') {
  79.                 x = i;
  80.                 break;
  81.             }
  82.  
  83.         }
  84.         //cout << "q.front = " << indtostr[ind] << endl;
  85.         for (int i = 0; i < 4; i++) {
  86.             int nx = x + dx[i];
  87.             if (nx >= 0 && nx < 9) {
  88.                 if (x % 3 == 2 && dx[i] == 1 || x % 3 == 0 && dx[i] == -1)
  89.                     continue;
  90.                 string t = cur;
  91.  
  92.                 swap(t[x], t[nx]);
  93.                 if (strtoind.count(t) == 0) {
  94.                     strtoind[t] = index;
  95.                     indtostr[index] = t;
  96.                     index++;
  97.                     was.push_back(0);
  98.                     p.push_back(0);
  99.                     steps.push_back(0);
  100.                 }
  101.                 int nind = strtoind[t];
  102.                 if (!was[nind]) {
  103.                     //cout << "new string t = " << t;
  104.                     was[nind] = 1;
  105.                     q.push( nind );
  106.                     p[nind] = strtoind[cur];
  107.                     //cout << "   p[nind] = " << p[nind] << "     ";
  108.                     steps[nind] = steps[strtoind[cur]] + 1;
  109.                     //cout << "   steps[nind] = " << steps[nind] << endl;
  110.                     if (t == ansstr)
  111.                         return;
  112.                 }
  113.             }
  114.         }
  115.     }
  116. }
  117.  
  118. int main() {
  119.  
  120.     indtostr[0] = ansstr;
  121.     strtoind[ansstr] = 0;
  122.     index++;
  123.  
  124.     cout << "Enter the combination:\n";
  125.  
  126.     vector<int> pred(index), was(index), steps(index);
  127.  
  128.     string t;
  129.     for (int i = 0; i < 3; i++) {
  130.         string te;
  131.         cin >> te;
  132.         t += te;
  133.     }
  134.     if (t == ansstr) {
  135.         cout << "That's the answer";
  136.         return 0;
  137.     }
  138.     clock_t start = clock();
  139.     bfs(t, pred, was, steps);
  140.  
  141.     if (steps[strtoind[ansstr]] == 0) {
  142.         cout << "No solution";
  143.         return 0;
  144.     }
  145.  
  146.     vector<int> ans;
  147.  
  148.     index = strtoind[ansstr];
  149.  
  150.     while (index != strtoind[t]) {
  151.         ans.push_back(index);
  152.         index = pred[index];
  153.     }
  154.  
  155.     reverse(begin(ans), end(ans));
  156.  
  157.  
  158.     for (int i = 0; i < ans.size(); i++) {
  159.         string t = indtostr[ans[i]];
  160.         for (int i = 0; i < 9; i += 3) {
  161.             for (int j = 0; j < 3; j++)
  162.                 cout << t[i + j];
  163.             cout << endl;
  164.         }
  165.         cout << endl;
  166.     }
  167.  
  168.     clock_t end = clock();
  169.     double seconds = (double)(end - start) / CLOCKS_PER_SEC;
  170.     cout << "time: " << seconds << endl << endl;
  171.     cout << "You need " << steps[strtoind[ansstr]] << " step(s)" << endl;
  172.  
  173.  
  174.     return 0;
  175. }
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
 
Top