题目描述

3x2 的格子

在其中放 5 张牌，其中 A 代表关羽，B 代表张飞，* 代表士兵。

还有一个格子是空着的。

你可以把一张牌移动到相邻的空格中去(对角不算相邻)。

游戏的目标是：关羽和张飞交换位置，其它的牌随便在哪里都可以。

样例

输入样例1：
* A
**B
输出样例1：
17

思路：八数码

(类似题：九宫重排(蓝桥杯历届试题))

C++ 代码

#include <bits/stdc++.h>

using namespace std;

string a[5];
int start, e;

int bfs(string s)
{
    queue<string> q;
    q.push(s);

    map<string, int> d;
    d[s] = 0;

    int dx[5] = {-1, 1, 0, 0}, dy[5] = {0, 0, 1, -1};

    while (q.size())
    {
        string t = q.front();
        q.pop();

        int k1 = t.find("A"), k2 = t.find("B");

        if (k1 == e && k2 == start)
        {
            return d[t];
        }

        int distance = d[t];
        int k = t.find(" ");
        int x = k / 3, y = k % 3;

        for (int i = 0;i < 4;i ++)
        {
            int a = x + dx[i], b = y + dy[i];

            if (a >= 0 && a < 2 && b >= 0 && b < 3)
            {
                swap (t[a * 3 + b], t[k]);

                if (!d.count(t))
                {
                    q.push (t);
                    d[t] = distance + 1;
                }

                swap (t[a * 3 + b], t[k]);
            }
        }
    }

    return -1;
}

int main()
{
    string s;
    for (int i = 0;i < 2;i ++)
    {
        getline (cin, a[i]);
        s += a[i];
    }

    for (int i = 0;i < 2;i ++)
    {
        for (int j = 0;j < 3;j ++)
        {
            if (a[i][j] == 'A') start = i * 3 + j;
            if (a[i][j] == 'B') e = i * 3 + j;
        }
    }

    cout << bfs(s) << endl;

    return 0;
}