1198 . 8-puzzle

題目連結: https://tioj.ck.tp.edu.tw/problems/1198

# 內容

請找出在 8-puzzle 遊戲中，從初始盤面至最終盤面最少需要移動的方格數。每一個方格一次只能移至相鄰的空格中。例如在下面的圖例中，從初始盤面至最終盤面最少需要移動 4 個方格。

1 2 3　　　1 2 3　　　　1 2 3　　　　1 2 3　　　 　1 2 3

4 8 5　　　4 8 5　　　　4 0 5　　　　4 5 0　　　 　4 5 6

7 6 0　　　7 0 6　　　　7 8 6　　　　7 8 6　　 7 8 0

初始盤面　第一步結果　第二步結果 　第三步結果　　第四步結果 (最終盤面)

# 解題思路

使用 BFS 將每一種轉換都記錄下來，每一種轉換需要用的步數用 map 對應，至找到答案後輸出
map<vector, int> D; -> vector 對應 數字 (步數)

# 程式碼

#include <bits/stdc++.h>
using namespace std;
map<vector<int>, int> D;
queue<vector<int>> Q;
int main(){
	ios::sync_with_stdio ( false ); cin.tie(0);
	int x;
	vector<int> st, ed;
	for ( int i=0; i<9; ++i ){
		cin >> x;
		st.emplace_back(x);
	}
	for ( int i=0; i<9; ++i ){
		cin >> x;
		ed.emplace_back(x);
	}
	D[st] = 1;
	Q.push(st);
	
	while ( !Q.empty() ){
		vector<int> x = Q.front(); Q.pop();
		int pos = 0, curd = D[x];
		while ( x[pos] ) pos++; //空格
		if ( pos >= 3 ) { // 向上
			swap(x[pos], x[pos-3]);
			if ( !D[x] ) D[x] = curd+1, Q.push(x);
			if ( x == ed ) break;
			swap(x[pos], x[pos-3]);
		}
		if ( pos <= 5 ) { // 向下
			swap(x[pos], x[pos+3]);
			if ( !D[x] ) D[x] = curd+1, Q.push(x);
			if ( x == ed ) break;
			swap(x[pos], x[pos+3]);
		}
		if ( pos%3 ) { // 向右
			swap(x[pos], x[pos-1]);
			if ( !D[x] ) D[x] = curd+1,Q.push(x);
			if ( x == ed ) break;
			swap(x[pos], x[pos-1]);
		}
		if ( pos%3!=2 ) { // 向左
			swap(x[pos], x[pos+1]);
			if ( !D[x] ) D[x] = curd+1,Q.push(x);
			if ( x == ed ) break;
			swap(x[pos], x[pos+1]);
		}
	}
	cout << D[ed]-1 << '\n';
	return 0;
}