卡片换位

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

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

在其中放5张牌，其中A代表关羽，B代表张飞，* 代表士兵。
还有一个格子是空着的。

你可以把一张牌移动到相邻的空格中去(对角不算相邻)。
游戏的目标是：关羽和张飞交换位置，其它的牌随便在哪里都可以。

输入格式：
输入两行6个字符表示当前的局面

输出格式：
一个整数，表示最少多少步，才能把AB换位（其它牌位置随意）

例如，输入：
* A
**B

程序应该输出：
17

再例如，输入：
A B
***

程序应该输出：
12

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

 dfs，bfs都可以吧。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;
map<string,bool> mp;
char s[2][4] = {"000","000"};
int sx,sy,ax,ay,bx,by;
int ans = inf;
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
void dfs(int x,int y,int sum) {
    if(sum >= ans) return;
    if(s[ax][ay] == 'B' && s[bx][by] == 'A') {
        ans = sum;
        return;
    }
    for(int i = 0;i < 4;i ++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if(tx < 0 || ty < 0 || tx >= 2 || ty >= 3) continue;
        swap(s[x][y],s[tx][ty]);
        string t = string(s[0]) + s[1];
        if(!mp[t]) {
            mp[t] = 1;
            dfs(tx,ty,sum + 1);
            mp[t] = 0;
        }
        swap(s[x][y],s[tx][ty]);
    }
}
int main() {
    for(int i = 0;i < 2;i ++) {
        if(i) getchar();
        for(int j = 0;j < 3;j ++) {
            s[i][j] = getchar();
            if(s[i][j] == ' ') {
                sx = i;
                sy = j;
            }
            else if(s[i][j] == 'A') {
                ax = i;
                ay = j;
            }
            else if(s[i][j] == 'B') {
                bx = i;
                by = j;
            }
        }
    }
    dfs(sx,sy,0);
    cout<<ans;
    return 0;
}