题目来源：[蓝桥杯2016初赛 C++ C组H题

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

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

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

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

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

输入样例

• A
  **B
  A B

输出样例
17
12

问题分析
这是一个求最少移动的数量的题（题面没有讲清楚，BUG），用BFS来解决。
一种做法是，每个状态用字符串来存储，会稍微慢一些，好在规模小。
另外一种做法是，每个状态存储A、B和空格位置（坐标）来实现。

AC的C++语言程序如下：

/* LQ0132 卡片换位 */#include 
#include 
#include 
#include using namespace std;const int drow[] = {-1, 0, 1, 0};
const int dcol[] = {0, 1, 0, -1};const int R = 2, C = 3;
struct Node {int ar, ac, br, bc, sr, sc, step;
};char g[R][C + 1];
bool vis[R][C][R][C][R][C];int bfs(Node s)
{memset(vis, false, sizeof vis);vis[s.ar][s.ac][s.br][s.bc][s.sr][s.sc] = true;queue q;s.step = 0;q.push(s);while (!q.empty()) {Node t = q.front();q.pop();for (int i = 0; i < 4; i++) {int nr = t.sr + drow[i];int nc = t.sc + dcol[i];if (0 <= nr && nr < R && 0 <= nc && nc < C) {Node ns = t;ns.sr = nr;ns.sc = nc;ns.step++;if (nr == t.ar && nc == t.ac)ns.ar = t.sr, ns.ac = t.sc;if (nr == t.br && nc == t.bc)ns.br = t.sr, ns.bc = t.sc;if (ns.ar == s.br && ns.ac == s.bc && ns.br==s.ar && ns.bc==s.ac)return ns.step;if (vis[ns.ar][ns.ac][ns.br][ns.bc][ns.sr][ns.sc] == false) {vis[ns.ar][ns.ac][ns.br][ns.bc][ns.sr][ns.sc] = true;q.push(ns);}}}}return -1;
}int main()
{while (gets(g[0])) {gets(g[1]);Node s;for (int i = 0; i < R; i++)for (int j = 0; j < C; j++)if (g[i][j] == 'A')s.ar = i, s.ac = j;else if (g[i][j] == 'B')s.br = i, s.bc = j;else if (g[i][j] == ' ')s.sr = i, s.sc = j;cout << bfs(s) << endl;}return 0;
}

AC的C++语言程序如下：

/* LQ0132 卡片换位 */#include 
#include 
#include using namespace std;const int R = 2, C = 3;
string s, s1, s2;
int cnxa, cnxb;int drow[] = {-1, 0, 1, 0};
int dcol[] = {0, 1, 0, -1};int bfs()
{unordered_map m;queue q;q.push(s);m[s] = 0;while (!q.empty()) {string t = q.front();q.pop();if (t.find('A') == cnxb && t.find('B') == cnxa)return m[t];int k = t.find(' ');int r = k / C, c = k % C, d = m[t];for (int i = 0; i < 4; i++) {int nr = r + drow[i];int nc = c + dcol[i];if (0 <= nr && nr < R && 0 <= nc && nc < C) {swap(t[k], t[nr * C + nc]);if (m.count(t) == 0) {q.push(t);m[t] = d + 1;}swap(t[k], t[nr * C + nc]);}}}return -1;
}int main()
{while (getline(cin, s1) && getline(cin, s2)) {s = s1 + s2;cnxa = s.find('A');cnxb = s.find('B');cout << bfs() << endl;}return 0;
}