問題

D – 8 Puzzle on Graph

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

atcoder.jp

記録

• 2022/7/4 解法わからず。

解法

• あとで書く。

コード例

#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;
}