Shark_eater

Untitled

Oct 25th, 2021 (edited)
341
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. #include <unordered_map>
  4.  
  5. int main()
  6. {
  7.     std::string a = "0110";
  8.     std::string b = "1101";
  9.     int n = a.length();
  10.  
  11.     std::queue<std::string> state;
  12.     state.push(a);
  13.     std::unordered_map<std::string, int> oper;
  14.     oper[a] = 0;
  15.     while (!state.empty())
  16.     {
  17.         std::string s = state.front();
  18.         state.pop();
  19.         int ops = oper[s] + 1;
  20.         for (int l = 0; l < n; ++l)
  21.         {
  22.             for (int r = l; r < n; ++r) // reversing
  23.             {
  24.                 s[r] = '1' - s[r] + '0';
  25.                 if (oper.find(s) == oper.end())
  26.                 {
  27.                     state.push(s);
  28.                     oper[s] = ops;
  29.                 }
  30.             }
  31.             for (int j = l; j < n; ++j) // reversing back
  32.             {
  33.                 s[j] = '1' - s[j] + '0';
  34.             }
  35.         }
  36.     }
  37.     std::cout << oper[b];
  38.     return 0;
  39. }
RAW Paste Data