lanqiao.125卡片换位（2016年蓝桥杯C/C++省赛C组）

题目：

语法点：

1. unordered_map<string,int> dist; //存储图的不同状态及不同状态对应的步数

2. unordered_map的相关操作，详细见C++中的unordered_map用法详解-CSDN博客

dist.count(x)    //来寻找x出现的次数
dist.find(x)     //来查找x是否存在
//返回值是无符号数据

3. string的用法String用法详解-CSDN博客

易错点：

1. 判断范围时不要写错，不然蓝桥平台容易超时，判错

代码：

这个代码只能通过7个测试点（总共8个测试点），还有一个通过不了

//lanqiao.125卡片换位
//注意：cin>>不可读入空格 
#include<iostream>
#include<cstring>
#include<algorithm>
#include <unordered_map>   //区别 
#include<queue> 
using namespace std;
//定义三个字符串，定义存储A，B位置的下标
//方位
unsigned int index1,index2;
string str1,str2,s; 
int dx[]={0,-1,0,1},dy[]={-1,0,1,0};
unordered_map<string,int> dist; //存储图的不同状态及不同状态对应的步数
int bfs()
{
	//定义队列
	//初始化（这里不用）：坐标，路径，标记【看情况而定】 
	//push一开始的状态
	queue<string> q;
	dist[s]=0;     //初始步数为0； 
	q.push(s);
	
	/*bfs主要部分：
	 while(!q.empty())
	 	{
	 		1.初始进队列 
	 		1.递归出口；
			2. 主要部分：
				找到空格位置
				一维度转二维
				位置步数记录 
				for（）变换方位
					{
						越界判断if()
						交换
						if（）	
							放入新队列
							步数加1； 
						换回来 
					}
		}
	*/
	while(!q.empty())
		{
			string t=q.front();
			q.pop();
			if(t.find('A')==index2&&t.find('B')==index1)
				{
				/*	cout<<dist[t];
					break;	*/
					return dist[t];
				}
			int k=t.find(' ');
			int x=k/3,y=k%3;
			long long distance=dist[t];
			
			for(int i=0;i<4;i++)
				{
					int nx=x+dx[i],ny=y+dy[i];
					if(nx<0||nx>1||ny<0||ny>2)
						{
							continue;
						}
					swap(t[k],t[nx*3+ny]);  //nx*3+ny是把一维转成二维 
					if(!dist.count(t))
						{
							q.push(t);
							dist[t]=distance+1;
						}
					swap(t[k],t[nx*3+ny]);
				 } 
			
		 } 
	return -1;
}
int main()
{
	getline(cin,str1);
	getline(cin,str2);
	s=str1+str2;
	
	index1=s.find('A');
	index2=s.find('B');	
	cout << bfs();
	return 0;
	
 }