第一次写bfs -_-

实在想不出怎么标记已访问的点，只好加在状态变量里了

C++ 代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

char a[3][4];
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int x1,y1,x2,y2,x3,y3;  //记录初始AB和空格的坐标
struct node{
    char m[3][4];  //当前状态矩阵
    int x,y;    //当前空格坐标
    int x1,y1;  //当前不能移动的点(上一步刚刚移动)
    int step;  //步数
}now;


int bfs(node r){
    queue<node> q;
    q.push(r);
    while(!q.empty()){
        now=q.front();
        q.pop();
        for(int i=0; i<4; i++){
            node next;
            next.x=now.x+dx[i];
            next.y=now.y+dy[i];
            if(next.x>2|| next.x<1|| next.y>3|| next.y<1|| (next.x==now.x1&&next.y==now.y1))continue;
            //下一步空格坐标越界或者为不可移动的点则退出
            memcpy( next.m,now.m,sizeof(now.m) ); 
            swap( next.m[now.x][now.y], next.m[now.x+dx[i]][now.y+dy[i]] );  //移动
            next.step = now.step + 1;
            if( next.m[x1][y1]=='B' && next.m[x2][y2]=='A' )return next.step;  //终止条件
            next.x1 = now.x;   next.y1 = now.y;  //标记移动过的点
            q.push(next);
        }
    }
}
int main(){
    string s1,s2;
    getline(cin,s1);  //读带空格字符串
    getline(cin,s2);
    s1+=s2;
    for(int i=1; i<=2; i++){  
       for(int j=1; j<=3; j++){
            a[i][j] = *s1.substr((i-1)*3+j-1,1).c_str();  //将字符串值存入数组
            if(a[i][j]=='A'){ x1=i; y1=j; }
            if(a[i][j]=='B'){ x2=i; y2=j; }
            if(a[i][j]==' '){ x3=i; y3=j; }
        }
    }
    now.x1=0; now.y1=0; now.x=x3; now.y=y3;
    memcpy(now.m,a,sizeof(a));
    cout<<bfs(now);
    return 0;
}