题目描述

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
string a[2];
string s1;
int startx,endx;
int xx,yy;
struct node
{
    int x,y,step;
    string s;
}Node;
int change(int x,int y)
{
    return x*3+y;
}
void bfs(int x,int y)
{
    map<string,int> mp;
    mp[s1]=1;
    Node.x=x;
    Node.y=y;
    Node.step=0;
    Node.s=s1;
    queue<node> q;
    q.push(Node);
    while(!q.empty())
    {
        node top=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int tempx=top.x+dx[i];
            int tempy=top.y+dy[i];
            string str=top.s;
            int index1,index2;
            index1=change(top.x,top.y);
            index2=change(tempx,tempy);
            swap(str[index1],str[index2]);
            if(tempx>=0&&tempx<2&&tempy>=0&&tempy<3&&!mp[str])
            {
                node m;
                m.x=tempx;
                m.y=tempy;
                m.step=top.step+1;
                m.s=str;
                mp[str]=1;
                if(m.s[startx]=='B'&&m.s[endx]=='A')
                {
                    cout<<m.step<<endl;
                    return;
                }
                q.push(m);
            } 
        }
    }
}
int main(void)
{
    getline(cin,a[0]);
    getline(cin,a[1]);
    s1=a[0]+a[1];
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<3;j++)
        {
            if(a[i][j]==' ')
            {
                xx=i;
                yy=j; 
            } 
            if(a[i][j]=='A')
            {
                startx=change(i,j);
            }
            if(a[i][j]=='B')
            {
                endx=change(i,j);
            }
        }
    }
    bfs(xx,yy);
    return 0;
}