你玩过华容道的游戏吗？这是个类似的，但更简单的游戏。看下面 3 x 2 的格子

+---+---+---+
| A | * | * | 
+---+---+---+
| B |　 | * |
+---+---+---+

在其中放5张牌，其中A代表关羽，B代表张飞，* 代表士兵。还有一个格子是空着的。你可以把一张牌移动到相邻的空格中去(对角不算相邻)。
游戏的目标是：关羽和张飞交换位置，其它的牌随便在哪里都可以。

输入：

输入存在多组测试数据，对于每组测试数据：
输入两行6个字符表示当前的局面

输出：

对于每组测试数据输出一个整数表示答案

样例输入：

* A
**B
A B
***

样例输出：

17
12

思路：

这个题我用了string 类来储存他的图，因为只有两行。
但是记录他的状态是问题要思考的一点，这里用了set进行判断，看看某种状态set中是否储存过，如果储存则直接跳过即可。
为什么我再s1 s2中间加了一个其他字符，这是因为在运用数组进行移动时，可以不用特意区分一二行的连接处，如果不加这个字符的话，用到数组进行方向移动时就会出现第一行的末尾直接移动到第二行初的情况。

代码：

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#define maxn 1000005
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;

struct wazxy{
    int x;
    string s;
    int steps;
}node,temp;
int A,B;
queue <wazxy> q;
int dx[4]={1,-1,4,-4};

void bfs(string ss,int x){
    set <string>  s;
    s.insert(ss);
    temp.s=ss,temp.steps=0,temp.x=x;
    q.push(temp);
    while(!q.empty()){
        temp=q.front();
        q.pop();
        if(temp.s[A]=='B'&&temp.s[B]=='A'){
            cout<<temp.steps<<endl;
            return ;
        }
        for(int i=0;i<4;i++){
            int nowx=temp.x+dx[i];
            if((nowx<3&&nowx>=0)||(nowx<=6&&nowx>=4)){
                node.steps=temp.steps+1;
                node.s=temp.s;
                node.x=nowx;
                node.s[temp.x]=temp.s[nowx];
                node.s[nowx]=' ';
                if(s.count(node.s)==0){
                    q.push(node);
                    s.insert(node.s);
                }
            }
        }
    }

}
int main(){
    string s1,s2,s3;
    while(getline(cin,s1)){
        while(!q.empty()) q.pop();
        getline(cin,s2);
        s3=s1+'#'+s2;
        int pos;
        for(int i=0;i<7;i++){
            if(s3[i]=='A')  A=i;
            if(s3[i]=='B')  B=i;
            if(s3[i]==' ')  pos=i;
        }
        bfs(s3,pos);
    }
    return 0;
}