# 【TIOJ】1198. 8-Puzzle

## [題目連結](https://tioj.ck.tp.edu.tw/problems/1198)

## **時間複雜度**

* $O(1 \approx 9!)$

## **解題想法**

這題的分類歸類到枚舉中的隱式圖中，他的解法是將每個可能的狀態當成一個節點，然後再用 BFS 去搜步數最少的解，最後輸出就可以了

實作上需要注意的地方有

1. `visited` 改成用 `map<vector<int>, int>` 去存
2. 最後答案一定會在 `used[{target_vector}]` 中

## **完整程式**

/* Question : TIOJ 1198. 8-puzzle */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pirq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second
#define int long long

#define n 9

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 9 + 50;
const int Mod = 1e9 + 7;
map<vector<int>, int> used;
queue<vector<int>> q;
vector<int> st, ed;

signed main(){
	opt;
	int x;
	st.resize(10);
	ed.resize(10);
	for ( int i = 0 ; i < n ; i++ ) cin >> st[i];
	for ( int i = 0 ; i < n ; i++ ) cin >> ed[i];
	q.push(st);
	
	while ( !q.empty() ){
		vector<int> cnt = q.front(); 
        	q.pop();
		int emp = 0, cntd = used[cnt];

		while ( cnt[emp] ) emp++; // Find the Empty Space

		if ( emp >= 3 ) { // If Available to Go Up
			swap( cnt[emp], cnt[emp-3] );
			if ( !used[cnt] ){
                		used[cnt] = cntd+1;
                		q.push(cnt);
            		}
			if ( cnt == ed ) break;
			swap( cnt[emp], cnt[emp-3] );
		}

		if ( emp <= 5 ) { // If Available to Go Down
			swap(cnt[emp], cnt[emp+3]);
			if ( !used[cnt] ){
                		used[cnt] = cntd+1;
                		q.push(cnt);
            		}
			if ( cnt == ed ) break;
			swap(cnt[emp], cnt[emp+3]);
		}

		if ( emp % 3 != 0 ) { // If Available to Go Right
			swap(cnt[emp], cnt[emp-1]);
			if ( !used[cnt] ){
                		used[cnt] = cntd+1;
                		q.push(cnt);
            		}
			if ( cnt == ed ) break;
			swap(cnt[emp], cnt[emp-1]);
		}

		if ( emp % 3 != 2 ) { // If Available to Go Left
			swap(cnt[emp], cnt[emp+1]);
			if ( !used[cnt] ){
                		used[cnt] = cntd+1;
                		q.push(cnt);
            		}
			if ( cnt == ed ) break;
			swap(cnt[emp], cnt[emp+1]);
		}
	}
	cout << used[ed] << "\n";
	return 0;
}