八数码 BFS扩展 存储字符串

⬅ 返回

1、例题

2、分析

需要用到的数据结构

3、代码

#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
 
 
queue<string> q;//存储可能的状态 
unordered_map<string,int> d;//到达该状态所需要的距离
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
string endstr="12345678x";
 
 
int bfs(string s){
	//初始化 
	q.push(s);
	d[s]=0;
	
	//bfs 
	while(q.size())
	{
		//取字符串 
		string  t = q.front();q.pop();
		//如果该字符串是目标字符串 返回
	    if(t==endstr)
			return d[t];
		
		//找x位置
		int posit = t.find('x');
		//一维坐标向二维坐标转换
		/*
			0-->(0,0)
			1-->(0,1)
			2-->(0,2)
			3-->(1,0)...	
		*/
		//横坐标
		int x = posit/3;
		//纵坐标 
		int y = posit%3;
		//对于x可能上下左右四个方向的移动进行遍历 
		for(int i=0;i<4;i++)
		{
			int a = x+dx[i];
			int b = y+dy[i];
			//二维向一维
			int posit2 = a*3+b; 
			//当该坐标未出界时 求出更新后的字符串copy 
			if(a>=0 && a<=2 && b>=0 && b<=2)
			{
				string copy = t;
				swap(copy[posit],copy[posit2]);
				//判断该字符串copy是否更新过距离 如果没有更新过 加入队列
				if(d[copy]==0)
				{
					q.push(copy);
					d[copy]=d[t]+1; 
				}
			} 	
		}
		
	}
	return -1;
	
	
	
}
 
int main(){
	
	string start;
	for(int i=1;i<=9;i++){
		char c;
		cin>>c;
		start=start+c;
	}
	cout<<bfs(start)<<endl;
	
	
}