[ABC224] D - 8 Puzzle on Graph

[Q] https://atcoder.jp/contests/abc224/tasks/abc224_d

見えてる地雷問題。やる前から重い実装だなと思う。1500msくらいになりました。

盤面の状態が9! = 362880 通りしかないので、盤面の状態を
map[ 9! をhashにしたもの ] = 何ターン目で到達？
でメモしていけば、せいぜい362880通りの探索とわかります。

1. 入力をもとにスタート地点を整理する。
2. 空きマスを探す。 0~7 を指定の数値。8を空きマスとみなす
3. map[ hash ] = turn でメモしながらbfs。
4. {0, 1, 2, ..., 8} の状態になったら終了。

Q. 
5
1 2
1 3
1 9
2 9
3 9
3 9 2 4 5 6 7 8


0. グラフを張る
0-indexed として、
G[0] = {1, 2, 8}
G[1] = {0, 8}
G[2] = {0, 8}
G[8] = {0, 1, 2}

1. startを作る。
3 9 2 4 5 6 7 8
なので、0-indexed にして
start[2] = 0
start[8] = 1
start[1] = 2
start[3] = 3
start[4] = 4
start[5] = 5
start[6] = 6
start[7] = 7

が入ります。

2. 空きマスは？
index 0 が未使用なので、
start[0] = 8 // 8:blank

start = { 8 2 0 3 4 5 6 7 1 }
として、bfsの初期値をセットします。
これが  { 0 1 2 3 4 5 6 7 8 } になれば、その時のturn数が解答。

Q.push(start)
MP[start] = 0 turn

3. bfsで探索。

turn / 状態
 0  { 8 2 0 3 4 5 6 7 1 }

・blank = 0 indexなので、
G[0] = {1, 2, 8}
 1  { 2 8 0 3 4 5 6 7 1 } // swap(v[0], v[1])
 1  { 0 2 8 3 4 5 6 7 1 } // swap(v[0], v[2])
 1  { 1 2 0 3 4 5 6 7 8 } // swap(v[0], v[8])

 2  { 2 1 0 3 4 5 6 7 8 }
 2  { 0 2 1 3 4 5 6 7 8 }
 2  { 1 8 0 3 4 5 6 7 2 }
 2  { 1 2 8 3 4 5 6 7 0 }

 3  { 8 1 0 3 4 5 6 7 2 }
 3  { 2 1 8 3 4 5 6 7 0 }
 3  { 8 2 1 3 4 5 6 7 0 }
 3  { 0 8 1 3 4 5 6 7 2 }

 4  { 0 1 8 3 4 5 6 7 2 }
 4  { 8 1 2 3 4 5 6 7 0 }
 4  { 2 8 1 3 4 5 6 7 0 }
 4  { 8 0 1 3 4 5 6 7 2 }

 5  { 0 1 2 3 4 5 6 7 8 } // goal

A. 5

実装

map<vector<ll>, ll> MP;
vector<ll> G[10];
queue<vector<ll>> Q;

ll find_blank(vector<ll> v){ // 8 がblank
 rep(i, 9) if(v[i] == 8) return i;
 return -1;
}

int main(){
 cincout();
 
 ll M;
 cin >> M;
 rep(i, M){
   ll u, v;
   cin >> u >> v;
   --u, --v;
   G[u].push_back(v);
   G[v].push_back(u);
 }
 vector<ll> start(9);
 bool used[9]{};
 rep(i, 8){
   ll s;
   cin >> s;
   --s;
   start[s] = i;
   used[s] = true;
 }
 
 // 空きマス探し
 ll blank = -1;
 rep(i, 9) if(used[i] == false) blank = i;
 start[blank] = 8; // 8:blank
 
 // 初期セット
 Q.push(start);
 MP[start] = 0;
 
 // goalセット
 vector<ll> goal(9); // {012345678} がゴール。 8:blank
 rep(i, 9) goal[i] = i;
 
 // bfs探索
 ll turn = -1;
 while (!Q.empty()){
   ll sz = Q.size();
   ++turn;
   rep(i, sz){
     auto V = Q.front(); Q.pop();
     if (V == goal){ // goalだったら終了
       cout << turn << endl;
       return 0;
     }
     ll blank = find_blank(V);
     for(auto u: G[blank]){
       swap(V[blank], V[u]); // バックトラック
       if (MP.count(V) == false){
         MP[V] = turn + 1;
         Q.push(V);
       }
       swap(V[blank], V[u]); // バックトラック復元
     }
   }
 }
 cout << -1  << endl;
}

https://atcoder.jp/contests/abc224/submissions/26803804