Advertisement
unknown_0711

Untitled

Aug 3rd, 2022
901
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.68 KB | None | 0 0
  1.  
  2. #include "bits/stdc++.h"
  3.  
  4. using namespace std;
  5. #define ll               long long
  6. #define all(x)            (x).begin(),(x).end()
  7. #define test int t; cin>>t; while(t--)
  8. #define ZYAB ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  9. #define mod 1000000007
  10. #define int long long
  11. #define inf 1e17
  12. #define endl '\n'
  13. ll max(ll i , ll j) {
  14.     if (i > j)return i;
  15.     else return j;
  16. }
  17. ll min(ll i , ll j) {
  18.     if (i < j)return i;
  19.     else return j;
  20. }
  21. bool check;
  22. int xx[] = {0, 0, 1, -1};
  23. int yy[] = {1, -1, 0, 0};
  24. void print(vector< vector<int> >&p) {
  25.     for (int i = 0; i < 3; i++)
  26.     {
  27.         for (int j = 0; j < 3; j++)
  28.             cout << p[i][j] << " ";
  29.  
  30.         cout << endl;
  31.     }
  32.     cout << endl; cout << endl; cout << endl;
  33. }
  34. map< vector< vector<int> > , int> visited;
  35.  
  36. vector< vector< vector<int> > > ans;
  37. bool valid(int x, int y) {
  38.     if (x >= 0 && y >= 0 && x < 3 && y < 3)return true;
  39.     else return false;
  40. }
  41. bool dfs(int x, int y, vector< vector<int> >&cur, vector< vector<int> > &final)
  42. {
  43.     if (check)return false;
  44.     if (visited.find(cur) != visited.end())return false;
  45.     if (cur == final)
  46.     {
  47.         check = true;
  48.         return true;
  49.     }
  50.     visited[cur] = 1;
  51.     bool ret = false;
  52.     for (int i = 0; i < 4; i++) {
  53.         int x_c = x + xx[i], y_c = y + yy[i];
  54.         if (check == false && valid(x_c, y_c))
  55.         {
  56.             swap(cur[x_c][y_c], cur[x][y]);
  57.             if (check)return false;
  58.             if (dfs(x_c, y_c, cur, final)) {
  59.                 // print(cur);
  60.                 ans.push_back(cur);
  61.                 swap(cur[x_c][y_c], cur[x][y]);
  62.                 return true;
  63.             }
  64.             swap(cur[x_c][y_c], cur[x][y]);
  65.         }
  66.         else continue;
  67.         if (check)return false;
  68.     }
  69.     return ret;
  70. }
  71. void solve() {
  72.     int x, y;
  73.     vector< vector<int> > initial, final;
  74.     for (int i = 0; i < 3; i++)
  75.     {
  76.         vector<int> p;
  77.         int a;
  78.         for (int j = 0; j < 3; j++)
  79.         {
  80.             cin >> a;
  81.             if (a == -1)x = i, y = j;
  82.             p.push_back(a);
  83.         }
  84.         initial.push_back(p);
  85.     }
  86.  
  87.     for (int i = 0; i < 3; i++)
  88.     {
  89.         vector<int> p;
  90.         for (int j = 0; j < 3; j++)
  91.         {
  92.             int a;
  93.             cin >> a;
  94.             p.push_back(a);
  95.         }
  96.         final.push_back(p);
  97.     }
  98.     check = false;
  99.  
  100.     dfs(x, y, initial, final);
  101.     ans.push_back(initial);
  102.     reverse(all(ans));
  103.     for (auto i : ans)print(i);
  104. }
  105.  
  106. signed main()
  107. {
  108.     ZYAB
  109. #ifndef ONLINE_JUDGE
  110.     freopen("input.txt", "r", stdin);
  111.     freopen("output.txt", "w", stdout);
  112.  
  113. #endif
  114. // ---------------------------------|--|------------------------------------
  115. // ---------------------------------|--|------------------------------------
  116. // ---------------------------------|--|------------------------------------
  117. // ---------------------------------|--|------------------------------------
  118. // ---------------------------------|--|------------------------------------
  119.  
  120.     solve();
  121.  
  122.  
  123.  
  124.  
  125. }
  126.  
  127.  
  128.  
  129.  
  130.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement