做的第二道Ru Jia Liu's Present系列里的题目，感觉这个系列里的题目不是难就是烦人……

这个也许算是系列中简单的题目之一了（尽管我RE了很多次），只能用普通BFS求解。虽然题目时限是10s，但是暴力做肯定会超时，因为BFS当中存重复状态的数组，如果用map/set表示的话就太慢了。

如果用一个数组 isuse[i]isuse[i] 表示第 ii 位的状态，0表示空位、1表示石头、2表示机器人呢？在存状态时就可以看作一个三进制数来用数组存，可惜这个三进制数最大（211111111111110211111111111110）大概是一千多万（十进制），数组大小依然有点危险。

所以只能用二进制存了，每位为1表示有机器人或石头，0表示有空位。但要再开一维表示机器人的位置，这样就不爆空间了。

但还要输出路径。代码仓库里是用位运算提取出不同的两位，但我太弱了想不到这个QAQ。我是将每个状态用一个不相同的编号 idid 表示，mueve[id]mueve[id] 表示 idid 这个状态的移动方法，这样递归输出时就只用考虑 idid 了。

代码：

#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
struct State {
    int dep, robot_pos, isuse, id;
    //dep表示步数，isuse表示状态
} start;
struct Move {
    int from, to;
} mueve[500003];//亲测开到这么大能过
std::queue<State> q;
bool vis[17][32771];//存状态
std::vector<int> e[17];//这里用vector存图
int fa[500003];//fa[id]是id的前驱节点
int T, n, m, s, t, ID;//ID是编号的最大值
void print(int st) {//输出路径
    std::vector<int> nodes;
    while (fa[st] != -1) {
        nodes.push_back(st);
        st = fa[st];
    }
    for (int i = nodes.size() - 1; i >= 0; i--)
        printf("%d %d\n", mueve[nodes[i]].from, mueve[nodes[i]].to);
}
void bfs(int s, int t) {
    while (!q.empty()) {
        State tmp = q.front();
        q.pop();
        if (tmp.robot_pos == t) {
            printf("%d\n", tmp.dep);
            print(tmp.id);
            return;
        }
        for (int i = 1; i <= n; i++)
            if (tmp.isuse & (1 << i - 1))
                for (int j = 0; j < e[i].size(); j++)
                    if (!(tmp.isuse & (1 << e[i][j] - 1))) {
                        State x = tmp;
                        x.isuse &= ~(1 << i - 1), x.isuse |= (1 << e[i][j] - 1);//移动
                        if (i == tmp.robot_pos)
                            x.robot_pos = e[i][j];
                        if (!vis[x.robot_pos][x.isuse]) {
                            vis[x.robot_pos][x.isuse] = 1;//第二次RE原因：看错变量，里面写错了
                            x.dep = tmp.dep + 1;
                            fa[x.id = ++ID] = tmp.id;//赋编号
                            mueve[ID] = (Move){i, e[i][j]};
                            q.push(x);
                        }
                    }
    }
    puts("-1");//记得加上
}
int main() {
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        memset(vis, 0, sizeof vis);
        memset(fa, -1, sizeof fa);//这个很重要
        memset(mueve, 0, sizeof mueve);
        for (int i = 0; i < 17; i++)
            e[i].clear();
        while (!q.empty())
            q.pop();
        //上面是初始化
        scanf("%d%d%d%d", &n, &m, &s, &t);
        start.robot_pos = s, start.isuse = 0;
        start.isuse |= (1 << s - 1);//一定要算上这个
        for (int i = 1; i <= m; i++) {
            int x;
            scanf("%d", &x);
            start.isuse |= (1 << x - 1);
        }
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            e[u].push_back(v), e[v].push_back(u);
        }
        ID = 0;//第一次RE原因：没加这个
        start.dep = 0, start.id = ++ID;
        printf("Case %d: ", cas);
        vis[s][start.isuse] = 1, q.push(start);
        bfs(s, t);
    }
    return 0;
}

写死我了