Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- signed main() {
- cin.tie(0)->sync_with_stdio(0);
- if (fopen("in", "r")) {
- freopen("in", "r", stdin);
- }
- vector<vector<int>> adj(10);
- int m; cin >> m;
- for (int i = 0; i < m; i++) {
- int u, v;
- cin >> u >> v;
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- vector<int> a(10);
- for (int i = 1; i <= 8; i++) {
- int x; cin >> x;
- a[x] = i;
- }
- int emp = -1;
- for (int i = 1; i <= 9; i++) {
- if (!a[i]) {
- emp = i;
- break;
- }
- }
- set<vector<int>> vst;
- queue<tuple<vector<int>,int,int>> q;
- q.push({a, emp, 0});
- while (q.size()) {
- vector<int> a = get<0>(q.front());
- int emp = get<1>(q.front());
- int cnt = get<2>(q.front());
- q.pop();
- if (vst.count(a)) continue;
- vst.insert(a);
- bool flag = true;
- for (int i = 1; i <= 9; i++) {
- if (i != emp && i != a[i]) {
- flag = false;
- break;
- }
- }
- if (flag) {
- cout << cnt << '\n';
- return 0;
- }
- for (auto &j : adj[emp]) {
- swap(a[emp], a[j]);
- q.push({a, j, cnt + 1});
- swap(a[emp], a[j]);
- }
- }
- cout << -1 << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement