蓝桥杯2016年C组：卡片换位

问题描述

你玩过华容道的游戏吗？
这是个类似的，但更简单的游戏。
看下面 3 x 2 的格子
+—--+—--+—--+
| A | * | * |
+--—+--—+—--+
| B | | * |
+--—+—--+--—+
在其中放5张牌，其中A代表关羽，B代表张飞，* 代表士兵。
还有一个格子是空着的。
你可以把一张牌移动到相邻的空格中去(对角不算相邻)。
游戏的目标是：关羽和张飞交换位置，其它的牌随便在哪里都可以。

输入格式：
输入两行6个字符表示当前的局面
输出格式：
一个整数，表示最少多少步，才能把AB换位（其它牌位置随意）

例如，输入：

* A
**B

程序应该输出：
17

再例如，输入：

A B
***

程序应该输出：
12

解决方案

思路

广度优先搜索

代码

#include <iostream>
#include <set>
#include <queue>

using namespace std;

struct OBJ {
    string buf;
    int index;
    int ans;

    OBJ(string _buf, int _index, int _ans) : buf(_buf), index(_index), ans(_ans) {}
};

set<string> log;
queue<OBJ> que;

bool check(string &buf, int indexA, int indexB) {
    return buf[indexA] == 'B' && buf[indexB] == 'A';
}

void pushNewBuf(OBJ &o, int toIndex) {
    string newBuf = o.buf;
    newBuf[o.index] = newBuf[toIndex];
    newBuf[toIndex] = ' ';
    //查重
    if (log.find(newBuf) == log.end()) {
        //记录
        log.insert(newBuf);
        que.push(OBJ(newBuf, toIndex, o.ans + 1));
    }
}

int fun(string &buf, int indexA, int indexB, int indexO) {
    log.insert(buf);
    que.push(OBJ(buf, indexO, 0));

    while (!que.empty()) {
        OBJ &front = que.front();

        //check
        if (check(front.buf, indexA, indexB)) {
            return front.ans;
        }

        if (front.index != 2 && front.index != 5) {
            pushNewBuf(front, front.index + 1);
        }
        if (front.index + 3 < 6) {
            pushNewBuf(front, front.index + 3);
        }
        if (front.index != 0 && front.index != 3) {
            pushNewBuf(front, front.index - 1);
        }
        if (front.index - 3 >= 0) {
            pushNewBuf(front, front.index - 3);
        }

        que.pop();
    }

    return 0;
}


int main() {

    string buf;
    int indexA = 0;
    int indexB = 0;
    int indexO = 0;
    for (int i = 0; i < 6;) {
        char c = getchar();
        if (c != '\n') {
            buf += c;
            if (c == 'A')
                indexA = i;
            else if (c == 'B')
                indexB = i;
            else if (c == ' ')
                indexO = i;

            ++i;
        }
    }
    getchar();

    cout << fun(buf, indexA, indexB, indexO);
    return 0;
}