Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- #define ll long long
- #define all(x) (x).begin(),(x).end()
- #define test int t; cin>>t; while(t--)
- #define ZYAB ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
- #define mod 1000000007
- #define int long long
- #define inf 1e17
- #define endl '\n'
- ll max(ll i , ll j) {
- if (i > j)return i;
- else return j;
- }
- ll min(ll i , ll j) {
- if (i < j)return i;
- else return j;
- }
- bool check;
- int xx[] = {0, 0, 1, -1};
- int yy[] = {1, -1, 0, 0};
- void print(vector< vector<int> >&p) {
- for (int i = 0; i < 3; i++)
- {
- for (int j = 0; j < 3; j++)
- cout << p[i][j] << " ";
- cout << endl;
- }
- cout << endl; cout << endl; cout << endl;
- }
- map< vector< vector<int> > , int> visited;
- vector< vector< vector<int> > > ans;
- bool valid(int x, int y) {
- if (x >= 0 && y >= 0 && x < 3 && y < 3)return true;
- else return false;
- }
- bool dfs(int x, int y, vector< vector<int> >&cur, vector< vector<int> > &final)
- {
- if (check)return false;
- if (visited.find(cur) != visited.end())return false;
- if (cur == final)
- {
- check = true;
- return true;
- }
- visited[cur] = 1;
- bool ret = false;
- for (int i = 0; i < 4; i++) {
- int x_c = x + xx[i], y_c = y + yy[i];
- if (check == false && valid(x_c, y_c))
- {
- swap(cur[x_c][y_c], cur[x][y]);
- if (check)return false;
- if (dfs(x_c, y_c, cur, final)) {
- // print(cur);
- ans.push_back(cur);
- swap(cur[x_c][y_c], cur[x][y]);
- return true;
- }
- swap(cur[x_c][y_c], cur[x][y]);
- }
- else continue;
- if (check)return false;
- }
- return ret;
- }
- void solve() {
- int x, y;
- vector< vector<int> > initial, final;
- for (int i = 0; i < 3; i++)
- {
- vector<int> p;
- int a;
- for (int j = 0; j < 3; j++)
- {
- cin >> a;
- if (a == -1)x = i, y = j;
- p.push_back(a);
- }
- initial.push_back(p);
- }
- for (int i = 0; i < 3; i++)
- {
- vector<int> p;
- for (int j = 0; j < 3; j++)
- {
- int a;
- cin >> a;
- p.push_back(a);
- }
- final.push_back(p);
- }
- check = false;
- dfs(x, y, initial, final);
- ans.push_back(initial);
- reverse(all(ans));
- for (auto i : ans)print(i);
- }
- signed main()
- {
- ZYAB
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- // ---------------------------------|--|------------------------------------
- // ---------------------------------|--|------------------------------------
- // ---------------------------------|--|------------------------------------
- // ---------------------------------|--|------------------------------------
- // ---------------------------------|--|------------------------------------
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement