/*
问题描述：
初始状态为：
1 2 3
4 5 6
7 8 0

输入最终状态，求初始状态到最终状态的步数；
如果步数小于等于5，则输出步数；否则输出-1
*/

#include "iostream"
#include "string"
#include "queue"
#include "vector"
#include "algorithm"
using namespace std;

const int direction[4][2] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };  //0移动的方向
const string init = "123456780"; //初始状态
const int num = 3; 
struct Node{
	string state;
	int depth; //到这一节点的步数
	int zero; //0的位置
	Node(int d = 0, string s = "", int z = 8) :depth(d), state(s), zero(z){}
};

int main(int argc, char *argv[]){
	int t;
	cin >> t; //测试用例的个数
	while (t--){
		string target = ""; //目标状态
		for (int i = 0; i < num * num; i++){
			string tmp;
			cin >> tmp;
			target += tmp;
		}
		queue<Node> openList;
		vector<string> closeList; //存放访问过的状态
		openList.push(Node(0, init, 8));
		
		int depth = 0;
		bool flag = false;
		while (!openList.empty() && depth <= 5){
			Node head = openList.front();
			depth = head.depth;
			if (head.state == target){
				flag = true;
				break;
			}
			int oldr = head.zero / num; //0所在的行
			int oldc = head.zero % num; //0所在的列
			for (int i = 0; i < 4; i++){
				int newr = oldr + direction[i][0];
				int newc = oldc + direction[i][1];
				if (newr >= 0 && newr < num && newc >= 0 && newc < num){
					int newpos = newr * 3 + newc; //0的新位置
					string newstate = head.state;
					newstate[head.zero] = head.state[newpos];
					newstate[newpos] = '0';
					if (find(closeList.begin(), closeList.end(), newstate) == closeList.end())
						openList.push(Node(head.depth + 1, newstate, newpos));
				}
			}
			openList.pop();
			closeList.push_back(head.state);
		}
		if (flag){
			cout << depth << endl;
		}
		else{
			cout << -1 << endl; //1 2 3 4 5 0 7 8 6
			//2  3  4  1  5  0  7  6  8
		}
	}
	return 0;
}

简单八数码问题