TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

8 Puzzle on Graph

問題

D – 8 Puzzle on Graph
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

// 19:42 47 20:13  

int main() {
  int M;
  cin >> M;

  vector<vector<int>> graph(10);

  rep(i, M) {
    int u, v;
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  string s = "999999999";
  rep(i, 8) {
    int p;
    cin >> p;
    s[p - 1] = (i + 1) + '0';
  }

  queue<string> que;
  que.push(s);
  map<string, int> mp;
  mp[s] = 0;

  while(que.size()) {
    string s2 = que.front();
    que.pop();
    rep(i, 9) {
      int t = 0;
      if(s2[i] == '9') {
        t = i + 1;
      }
      for(auto j: graph[t]) {
        string s3 = s2;
        swap(s3[j - 1], s3[t - 1]);
        if (mp.count(s3)) {
          continue;
        }
        mp[s3] = mp[s2] + 1;
        que.push(s3);
      }
    }
  }

  if (mp.count("123456789") == 0) {
    cout << -1 << endl;
  } else {
    cout << mp["123456789"] << endl;
  }
  return 0;
}