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