Advertisement
Josif_tepe

Untitled

Oct 30th, 2022
823
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <vector>
  5. #include <queue>
  6. #include <map>
  7. using namespace std;
  8.  
  9. struct pawn {
  10.     string S;
  11.     int distance;
  12.     vector<int> v;
  13. };
  14. bool check_if_pawns_are_ok(string &s) {
  15.     if(s[0] == '1') {
  16.         int idx = -1;
  17.         for(int i = 0; i < (int) s.size(); i++) {
  18.             if(s[i] != '1') {
  19.                 idx = i;
  20.                 break;
  21.             }
  22.         }
  23.         if(idx != -1) {
  24.             while(s[idx] == '0' and idx < (int) s.size()) {
  25.                 idx++;
  26.             }
  27.             for(int i = idx; i < (int) s.size(); i++) {
  28.                 if(s[i] != '2') {
  29.                     return false;
  30.                 }
  31.             }
  32.          
  33.         }
  34.         return true;
  35.     }
  36.     return false;
  37. }
  38. map<string, bool> visited;
  39. map<int, pair<string, int> > mapa;
  40. int main()
  41. {
  42.     ios_base::sync_with_stdio(false);
  43.     int n;
  44.     cin >> n;
  45.     vector<int> v(n);
  46.     string s = "";
  47.     for(int i = 0; i < n; i++) {
  48.         cin >> v[i];
  49.         s += (v[i] + '0');
  50.     }
  51.     queue<pawn> Q;
  52.     vector<int> emp;
  53.     visited[s] = true;
  54.     pawn tmp;
  55.     tmp.S = s;
  56.     tmp.distance = 0;
  57.     tmp.v = emp;
  58.     Q.push(tmp);
  59.    
  60.     while(!Q.empty()) {
  61.         tmp = Q.front();
  62.         Q.pop();
  63.         if(check_if_pawns_are_ok(tmp.S)) {
  64.             cout << tmp.distance << endl;
  65.             // print the steps
  66.             for(int i = 0; i < tmp.v.size(); i++) {
  67.                 cout << tmp.v[i] << " ";
  68.             }
  69.             return 0;
  70.         }
  71.         for(int i = 0; i < (int) tmp.S.size(); i++) {
  72.             if(tmp.S[i] == '1') {
  73.                 if(i - 1 >= 0 and tmp.S[i - 1] == '0') {
  74.                     string ps = tmp.S;
  75.                     ps[i] = '0';
  76.                     ps[i - 1] = '1';
  77.                     if(!visited[ps]) {
  78.                         visited[ps] = true;
  79.                         pawn new_pawn;
  80.                         new_pawn.S = ps;
  81.                         new_pawn.distance = tmp.distance + 1;
  82.                         vector<int> steps = tmp.v;
  83.                         steps.push_back(i + 1);
  84.                         new_pawn.v = steps;
  85.                         Q.push(new_pawn);
  86.                     }
  87.                 }
  88.                 if(i - 2 >= 0 and tmp.S[i - 1] != '0' and tmp.S[i - 2] == '0') {
  89.                     string ps = tmp.S;
  90.                     ps[i] = '0';
  91.                     ps[i - 2] = '1';
  92.                     if(!visited[ps]) {
  93.                         visited[ps] = true;
  94.                         pawn new_pawn;
  95.                         new_pawn.S = ps;
  96.                         new_pawn.distance = tmp.distance + 1;
  97.                         vector<int> steps = tmp.v;
  98.                         steps.push_back(i + 1);
  99.                         new_pawn.v = steps;
  100.                         Q.push(new_pawn);
  101.                     }
  102.                 }
  103.                
  104.             }
  105.             else if(tmp.S[i] == '2') {
  106.                 if(i + 1 < (int) tmp.S.size() and tmp.S[i + 1] == '0') {
  107.                     string ps = tmp.S;
  108.                     ps[i] = '0';
  109.                     ps[i + 1] = '2';
  110.                     if(!visited[ps]) {
  111.                         visited[ps] = true;
  112.                         pawn new_pawn;
  113.                         new_pawn.S = ps;
  114.                         new_pawn.distance = tmp.distance + 1;
  115.                         vector<int> steps = tmp.v;
  116.                         steps.push_back(i + 1);
  117.                         new_pawn.v = steps;
  118.                         Q.push(new_pawn);
  119.                     }
  120.                 }
  121.                 if(i + 2 < (int) tmp.S.size() and tmp.S[i + 1] != '0' and tmp.S[i + 2] == '0') {
  122.                     string ps = tmp.S;
  123.                     ps[i] = '0';
  124.                     ps[i + 2] = '2';
  125.                     if(!visited[ps]) {
  126.                         visited[ps] = true;
  127.                         pawn new_pawn;
  128.                         new_pawn.S = ps;
  129.                         new_pawn.distance = tmp.distance + 1;
  130.                         vector<int> steps = tmp.v;
  131.                         steps.push_back(i + 1);
  132.                         new_pawn.v = steps;
  133.                         Q.push(new_pawn);
  134.                     }
  135.                 }
  136.             }
  137.         }
  138.     }
  139.    
  140.    
  141.     return 0;
  142. }
  143.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement