题目链接：https://www.lanqiao.cn/problems/642/learning/

总体就是用了bfs，然后去维护之前的操作。
这个看了视频自己才写出来的，视频中提到“经过某几步到达一种状态  一般考虑到   dfs+set去重”
这也就是为什么考虑到使用bfs，而不是其他算法
用字符串进行比较，用set进行维护。

/*
总结  大概就是 bfs  然后去维护之前进行过的操作 
		经过某几步到达一种状态  一般考虑到   dfs+set去重 

*/
#include<bits/stdc++.h>
using namespace std;
char *start = "012345678";
char *target = "087654321";
struct StateAndLevel{
	char *state;
	int level;
	int pos0;
	//不知道是干什么用的，应该是让结构体以一种类似于函数调参的形式展现出来 
	StateAndLevel(char* _state,int _level,int _pos0):state(_state),level(_level),pos0(_pos0){}
};
queue<StateAndLevel> q;
struct cmp{//设置set的去重方式 
	bool operator()(char* a,char* b){
		return strcmp(a,b)<0;
	}
};
set<char*,cmp>allState;
void swap(char* k,int a,int b)//交换原有0位置和新0位置进行交换 
{
	char t=k[a];
	k[a]=k[b];
	k[b]=t;
}
void jiaohuan(char *state,int pos0,int newpos0,int le)
{
	char *new_state = (char*)malloc(9*sizeof(char));  //创建一个新的字符串 
	strcpy(new_state,state);//将原有字符串复制到新的串中 
	swap(new_state,pos0,newpos0);//交换指定位置 
	if(allState.find(new_state)==allState.end()) //去掉重复性操作 
	{
		allState.insert(new_state);//列入到历史记录中 
		q.push(StateAndLevel(new_state,le+1,newpos0));//列入到队列里 
	}
}
int main()
{
	q.push(StateAndLevel(start,0,0));//先将初始状态入列 
	allState.insert(start);//将初始状态计入历史 
	while(!q.empty())//当队列不为空时 
	{
		StateAndLevel sal = q.front();//取出队列首个元素 ，获取内容 
		char *state = sal.state;
		int le = sal.level;
		if(strcmp(state,target)==0)//当目前取出的队列中的元素符合条件时跳出 
		{
			cout<<le<<endl;
			return 0;
		} 
		int pos0 = sal.pos0;//获取0的位置 
		//交换
		int newpos0=(pos0-1+9)%9;//设置0的新位置 
		jiaohuan(state,pos0,newpos0,le);
		 newpos0=(pos0+1+9)%9;
		jiaohuan(state,pos0,newpos0,le);
		 newpos0=(pos0-2+9)%9;
		jiaohuan(state,pos0,newpos0,le);
		 newpos0=(pos0+2+9)%9;
		jiaohuan(state,pos0,newpos0,le);
		q.pop();
	}
	return 0;
 }